算法-背包DP

背包DP

引入

在具体讲何为背包dp前，先来看如下的例题：

题意概要：有 \(n\) 个物品和一个容量为 \(W\) 的背包，每个物品有重量 \(w_i\) 和价值 \(v_i\) 两种属性，要求选若干物品放入背包使得背包中的物品的总价格

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的0和1，这类问题便被称作0-1背包问题。

0-1背包

解释

例题中已知条件有第i个物品的重量\(w_i\) ，价值\(v_i\) 以及背包的总重量 \(W\)。

设DP状态 \(f_{i,j}\) 为在只能放前 \(i\) 个物品的情况下，容量为 \(j\) 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 \(i-1\) 个物品的情况下，那么对于第 \(i\) 个物品当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 \(f_{i-1,j}\) ；当其放入背包时，背包的剩余容量会减小 \(w_i\) 背包中物品的总价值会增大 \(v_i\) ，故这种情况的最大价值为 \(f_{i-1,j-w_{i}}+ v_i\)

由此可以得出状态转移方程： \[ f_{i,j} = max(f_{i-1,j},f_{i-1,j-w_i}+v_i) \] 这里如果直接采用二维数组对状态进行记录，会出现MLE。可以考虑改用滚动数组的形式来优化。由于对 \(f_i\) 有影响的只有 \(f_{i-1}\) , 可以去掉第一维，直接用 \(f_i\) 来表示处理到当前物品时背包容量为 \(i\) 的最大价值，得出以下方程: \[ f_j = max(f_j,f_{j-w_i}+v_i) \] 务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的。

实现

1
2
3
4
5
for(int i=1; i<=n; i++){
    for(int l= W; l>=w[i];l--){
        f[l] = max(f[l],f[l-w[i]]+ v[i]);
    }
}

完全背包

解释

完全背包模型与 \(0-1\) 背包类似，与 \(0-1\) 背包的区别仅在于一个物品可以选取无限次，而非仅能选择一次。

我们可以借鉴 \(0-1\) 背包的思路，进行状态定义：设 \(f_{i,j}\) 为只能选前 \(i\) 个物品时，容量为 \(j\) 的背包可以达到的最大价值。

需要注意的是，虽然定义与 \(0-1\) 背包类似，但是其状态转移方程和 \(0-1\) 并不相同。

过程

可以考虑一个朴素的做法：对于第 \(i\) 件物品，枚举其选了多少个来转移。这样做的时间复杂度时 \(O(n^3)\)的。

状态转移方程如下： \[ f_{i,j} = \max\limits_{k=0}^{+\infty} \left(f_{i-1,j-k\times w_i} + v_i\times k\right) \] 考虑做一个简单的优化。可以发现，对于 \(f_{i,j}\) ，只要通过 \(f_{j,j-w_i}\) 转移就可以了。因此状态转移方程为： \[ f_{i,j} = \max(f_{i-1,j}, f_{i,j-w_i}+v_i) \] 理由时当我们这样转移时，\(f_{i,j-w_i}\) 已经由 \(f_{i,j}-2\times w_i\) 更新过，那么 \(f_{i,j-w_i}\) 就是充分考虑了第 \(i\) 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。