DP | 背包问题

利用特殊性质实现背包的多次求解¶

「雅礼集训 2017 Day5」珠宝 /「NAIPC2016」Jewel Thief

给点01背包模型，当要求背包容量在\(1\sim k\)时的最大价值。

n≤1e6,k≤5e4,v_i≤300

思路¶

这里我们转移到物品的体积有很多是相同的。那么对于相同体积的物品，我们肯定是优先选择价值大的。现在的问题貌似就变成了一个不完全的多重背包了。

所以我们可以就按照多重背包来写，定义f_{i,j} 为在已经考虑了前i种物品，且背包占用体积为j时的最大价值

我们有转移

f_{i,j}=\max(f_{i-1,j-v_ik}+w(i,k))，其中w(i,k)为第i类物品（同一类物品即体积相等的物品）拿k个的最大价值，即贪心选择其中价值前k大的物品的价值和。

压维可以写成f_{j}=\max(f_{v-v_ik}+w(i,k))

那么应用决策单调性，首先我们得找到满足四边形不等式。那么我们只能从价值函数中看看了

首先我们的w(i,k)，我们对于每一个i都写成一个数组w_{i,k}，省略i维，那么其实就是一个一维的数组w_k。但是这样我们就不满足四边形不等式了。回顾DP | 区间dp中四边形不等式的条件。

那么我们怎么办？考虑**把一维的函数变为二维。**我们变换函数w_k为w'{j-k,j}，映射关系为f:w'。好了，接下来验证四边形不等式条件：交叉优于包含。}→w_{j-i

因为我们验证交叉优于包含的两种情况中的两个区间的长度和是一样的，也是转化回w数组，就变成了

那么很显然，w_i+w_j>w_l+w_r。

回到转移式，我们的决策点即k，那么现在j-k是单调的，转移也就单调了。

hole