0-1 背包¶

问题描述¶

有 \(n\) 个物品和一个容量为 \(W\) 的背包，每个物品有重量 \(w_i\) 和价值 \(v_i\) 两种属性，要求：选若干物品放入背包，使背包中物品的 总价值最大 且 背包中物品的总重量不超过背包的容量

状态转移方程¶

状态定义¶

设 f[i][j] 表示只考虑前 i 个物品时，容量为 j 的背包所能达到的最大总价值

状态转移¶

决策：每件物品只有放和不放两种可能的决策

考虑物品 i ：

如果不放入 i ，背包容量不变，所能达到的总价值和 i-1 件物品相同；
如果放入 i ，则背包容量要减去 i 的体积 w[i] ，总价值在 i-1 件的基础上加上所放物品的价值 v[i]

综上可得 状态转移方程：

f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

边界条件¶

背包问题的边界条件非常简单，dp 数组全部初始化为 0 就好了

不过要注意有一类变种：如果题目中附加了条件 “恰好装满背包” ，则初始化时除了 f[][0] 初始化为为 0 ，f[][1..V]均应设为 -INF

Note

几乎所有背包问题的初始化都是上面两种情况之一，所以在其他背包问题中不再考虑边界条件

规划方向¶

二维数组存储所有状态¶

先看 i ：很明显应该从小到大枚举 i

再看 j ：有 i 的存在，j 的枚举顺序随意

代码如下：

for(int i=1;i<=n;i++)
    for(int j=0;j<=W;j++)
        f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);

压缩至一维¶

我们还可以使用 滚动数组 技巧，丢掉 i ，将空间压缩至一维

但要注意，此时 j 应逆序枚举，原因如下：

已经遍历的被更新到状态 i ，没有遍历的维持 i-1 状态，我们要的 f[j-w[i]] 是 i-1 状态的，也就是说要保证更新 f[j] 的时候 f[j-w[i]] 还是 i-1 的状态的，所以要逆序枚举

从本质上来说，这是因为我们在在考虑第 i-1 件物品时只能做一次决策，做完这次决策就要立马考虑下一个物品 i ，否则就可以在同一个物品上做多次决策，而这是不允许的

代码如下：

for(int i=1;i<=n;i++)
    for(int j=W;j>=0;j--)
        f[j]=max(f[j],f[j-w[i]]+v[i]);

小优化¶

不叫优化的优化...

for(int i=1;i<=n;i++)
    for(int j=W;j>=w[i];j--)
        f[j]=max(f[j],f[j-w[i]]+v[i]);

看看真正的优化，在 W 较大的时候比较有用

对于最后一件物品 f[W] ，只要知道 f[W-w[n]] 即可；对于倒数第二件物品 f[W-w[n]] ，只要知道 f[W-w[n...n-1] 即可

依此类推，对于第 i 件物品，只要知道 f[W-w[n...i])] 即可，所以可以有如下操作：

for(int i=n;i>=1;i--)
    sum[i]+=w[i];
    // sum[i] 预处理成 i..n 物品的 w[i] 和
for(int i=1;i<=n;i++){
    bound=max(W-sum[i],w[i]);
    for(int j=W;j>=w[i];j--)
        f[j]=max(f[j],f[j-w[i]]+v[i]);
}