背包问题

程序设计

阅读《背包 9 讲》的简单笔记。

部分背包

物品可以拆分，只需要通过贪心算法即可求解。

01 背包

每个物品最多只能放一次。

f[i][v] = max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

滚动数组

for v = V .. 0
    f[v] = max{f[v],f[v-c[i]]+w[i]}

如果希望背包完全装满，那么将 $f[0] = -\inf, f[1..V] = 0$；如果只是希望价值尽量大，那么 $f[0..V] = 0$。

完全背包

每种物品可以放无限多次。

f[i][v] = max{ f[i-1][v-k*c[i]]+k*w[i] | 0<=k*c[i]<=v }

这是基本思路，虽然状态还是 O(NV) 个，但是求解状态不再是 O(1) 时间。

优化：

• 如果存在 w[i] < w[j] && c[i] > c[j] 可以去除物品 i。
• 直接去掉 c[i] > V 的物品，费用相同中，只取性价比最高的。

转移方程：

for i=1..N 
    for v=0..V // 此处不同
        f[v]=max{f[v],f[v-cost]+weight} // 利用重复选的性质。

或者

for i=1..N 
    for v=0..V
        f[i][v]=max{f[i-1][v],f[i][v-cost]+weight}

这个思路简直神奇。

多重背包

每种物品有一个固定的次数上限。

基本状态转移方程：

f[i][v] = max{f[i-1][v-k*c[i]] + k*w[i] | 0<=k<=n[i]}

思路可以简单地转化为 01 背包问题，将 n[i] 件物品直接拆分即可，程序清晰，然而并不降低复杂度。可以将 $n[i] = 1 + 2 + 4 + ... + 2^(k-1) + (n[i] - 2^k + 1)$ 拆分为 $k$ 件物品求解，复杂度下降为 $O(NV \log n[i])$.

存在 $O(NV)$ 时间的解法，但是平摊分析已经超出 NOIP 的范围（= =）。

二维代价

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

可以用 2 维数组实现，01背包则逆序，完全背包正序。