引入

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

题意概要：有\( 𝑛\) 个物品和一个容量为\( 𝑊\) 的背包，每个物品有重量 \(𝑤_𝑖\) 和价值 \(𝑣_𝑖\) 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量．

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

0-1背包

解释

例题中已知条件有第 \(𝑖\) 个物品的重量 \(𝑤_𝑖\)，价值 \(𝑣_𝑖\)，以及背包的总容量 \(𝑊\)．

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

考虑转移．假设当前已经处理好了前 \(𝑖 −1 \)个物品的所有状态，那么对于第 \(𝑖\) 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 \(𝑓_{𝑖−1,𝑗}\)；当其放入背包时，背包的剩余容量会减小 \(𝑤_𝑖\)，背包中物品的总价值会增大 \(𝑣_𝑖\)，故这种情况的最大价值为 \(𝑓_{𝑖−1,𝑗−𝑤_𝑖} +𝑣_𝑖\)．

由此可以得出状态转移方程：

\[𝑓_{𝑖,𝑗}=max(𝑓_{𝑖−1,𝑗},𝑓_{𝑖−1,𝑗−𝑤_𝑖}+𝑣_𝑖)\]

这里如果直接采用二维数组对状态进行记录，会出现 MLE．可以考虑改用滚动数组的形式来优化．

由于对 \(𝑓_𝑖 \)有影响的只有 \(𝑓_{𝑖−1}\)，可以去掉第一维，直接用 \(𝑓_𝑖 \)来表示处理到当前物品时背包容量为\( 𝑖\) 的最大价值，得出以下方程：

\[𝑓_𝑗=max(𝑓_𝑗,𝑓_{𝑗−𝑤_𝑖}+𝑣_𝑖)\]

务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的．

实现

还有一点需要注意的是，很容易写出这样的 错误核心代码：

for i in range(1, n + 1):
    for l in range(0, W - w[i] + 1):
        f[l + w[i]] = max(f[l] + v[i], f[l + w[i]])
# 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]], f[i - 1][l] + w[i]),
# f[i][l + w[i]]) 简化而来

这段代码哪里错了呢？枚举顺序错了．

仔细观察代码可以发现：对于当前处理的物品 \(𝑖\) 和当前状态 \(𝑓_{𝑖,𝑗}\)，在 \(𝑗 ⩾𝑤_𝑖\) 时，\(𝑓_{𝑖,𝑗}\) 是会被 \(𝑓_{𝑖,𝑗−𝑤_𝑖}\) 所影响的．这就相当于物品 \(𝑖 \)可以多次被放入背包，与题意不符．（事实上，这正是完全背包问题的解法）

为了避免这种情况发生，我们可以改变枚举的顺序，从 \(𝑊\) 枚举到 \(𝑤_𝑖\)，这样就不会出现上述的错误，因为 \(𝑓_{𝑖,𝑗}\) 总是在 \(𝑓_{𝑖,𝑗−𝑤_𝑖}\) 前被更新．

因此实际核心代码为

for i in range(1, n + 1):
    for l in range(W, w[i] - 1, -1):
        f[l] = max(f[l], f[l - w[i]] + v[i])

完全背包

解释

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

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

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

过程

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

状态转移方程如下：

\[f_{i,j} = \max_{k=0}^{+\infty} (f_{i-1, j - k \times w_i} + v_i \times k) \]

考虑做一个简单的优化．可以发现，对于\(𝑓_{𝑖,𝑗}\)，只要通过 \(𝑓_{𝑖,𝑗−𝑤_𝑖}\) 转移就可以了．因此状态转移方程为：

\[f_{i,j} = \max(f_{i-1,j}, f_{i,j-w_i} + v_i) \]

理由是当我们这样转移时，\(𝑓_{𝑖,𝑗−𝑤_𝑖}\) 已经由 \(𝑓_{𝑖,𝑗−2\times 𝑤_𝑖}\)更新过，那么 \(𝑓_{𝑖,𝑗−𝑤_𝑖}\) 就是充分考虑了第 \(𝑖\) 件物品所选次数后得到的最优结果．换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度．

与 0-1 背包相同，我们可以将第一维去掉来优化空间复杂度．如果理解了 0-1 背包的优化方式，就不难明白压缩后的循环是正向的（也就是上文中提到的错误优化）．

多重背包

多重背包也是 0-1 背包的一个变式．与 0-1 背包的区别在于每种物品有 \(𝑘_𝑖\) 个，而非一个．

一个很朴素的想法就是：把「每种物品选 \(𝑘_𝑖\) 次」等价转换为「有\(𝑘_𝑖\) 个相同的物品，每个物品选一次」．这样就转换成了一个 0-1 背包模型，套用上文所述的方法就可已解决．状态转移方程如下：

\[f_{i,j} = \max_{k=0}^{k_i} (f_{i-1, j - k \times w_i} + v_i \times k) \]

时间复杂度 \(𝑂(𝑊\sum _{𝑛_{𝑖=1}}^{𝑘_𝑖})\)．

Reference

动态规划——背包问题python实现（01背包、完全背包、多重背包）

背包 DP

#

!

引入

0-1背包

解释

实现

完全背包

解释

过程

多重背包

Reference