前言
今天是我们讲解动态规划专题中的「背包问题」的第四天。
在众多背包问题中「01 背包问题」是最为核心的，因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。
其中 01 背包的「一维空间优化」更是要重点掌握。
另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~
题目描述
有 NNN 种物品和一个容量为 CCC 的背包，每种物品都有无限件。
第 iii 件物品的体积是 v[i]v[i]v[i]，价值是 w[i]w[i]w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择多次的特点（在容量允许的情况下）。
示例 1：
输入: N = 2, C = 5, v = [1,2], w = [1,2] 输出: 5 解释: 选一件物品 1，再选两件物品 2，可使价值最大。 复制代码
常规解法
我们可以直接将 01 背包的「状态定义」拿过来用：
dp[i][j]dp[i][j]dp[i][j] 代表考虑前 iii 件物品，放入一个容量为 jjj 的背包可以获得的最大价值。
由于每件物品可以被选择多次，因此对于某个 dp[i][j]dp[i][j]dp[i][j] 而言，其值应该为以下所有可能方案中的最大值：
- 选择 0 件物品 iii 的最大价值，即 dp[i−1][j]dp[i-1][j]dp[i−1][j]
- 选择 1 件物品 iii 的最大价值，即 dp[i−1][j−v[i]]+w[i]dp[i-1][j-v[i]]+w[i]dp[i−1][j−v[i]]+w[i]
- 选择 2 件物品 iii 的最大价值，即 dp[i−1][j−2∗v[i]]+2∗w[i]dp[i-1][j-2*v[i]]+2*w[i]dp[i−1][j−2∗v[i]]+2∗w[i]
... - 选择 k 件物品 iii 的最大价值，dp[i−1][j−k∗v[i]]+k∗w[i]dp[i-1][j-k*v[i]]+k*w[i]dp[i−1][j−k∗v[i]]+k∗w[i]
由此我们可以得出「状态转移方程」为：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−k∗v[i]]+k∗w[i]),0<k∗v[i]⩽jdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * v[i]] + k * w[i]), 0 < k*v[i] \leqslant jdp[i][j]=max(dp[i−1][j],dp[i−1][j−k∗v[i]]+k∗w[i]),0<k∗v[i]⩽j
代码：
class Solution { public int maxValue(int N, int C, int[] v, int[] w) { int[][] dp = new int[N][C + 1]; // 先预处理第一件物品 for (int j = 0; j <= C; j++) { // 显然当只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件 int maxK = j / v[0]; dp[0][j] = maxK * w[0]; } // 处理剩余物品 for (int i = 1; i < N; i++) { for (int j = 0; j <= C; j++) { // 不考虑第 i 件物品的情况（选择 0 件物品 i） int n = dp[i - 1][j]; // 考虑第 i 件物品的情况 int y = 0; for (int k = 1 ;; k++) { if (j < v[i] * k) { break; } y = Math.max(y, dp[i - 1][j - k * v[i]] + k * w[i]); } dp[i][j] = Math.max(n, y); } } return dp[N - 1][C]; } } 复制代码
- 时间复杂度：共有 N∗CN * CN∗C 个状态需要被转移，但每次转移都需要枚举当前物品的件数，最多枚举 C 次（重量为最小值 1），因此整体复杂度为 O(N∗C∗C)O(N * C * C)O(N∗C∗C)
- 空间复杂度：O(N∗C)O(N * C)O(N∗C)
滚动数组
通过观察我们的「状态转移方程」可以发现，我们在更新某个 dp[i][x]dp[i][x]dp[i][x] 的时候只依赖于 dp[i−1][x]dp[i-1][x]dp[i−1][x]。
因此我们可以像 01 背包那样使用「滚动数组」的方式将空间优化到 O(C)O(C)O(C)。
代码：
class Solution { public int maxValue(int N, int C, int[] v, int[] w) { int[][] dp = new int[2][C + 1]; // 先预处理第一件物品 for (int j = 0; j <= C; j++) { // 显然当我们只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件 int maxK = j / v[0]; dp[0][j] = maxK * w[0]; } // 处理剩余物品 for (int i = 1; i < N; i++) { for (int j = 0; j <= C; j++) { // 不考虑第 i 件物品的情况（选择 0 件物品 i） int n = dp[(i - 1)&1][j]; // 考虑第 i 件物品的情况 int y = 0; for (int k = 1 ;; k++) { if (j < v[i] * k) { break; } y = Math.max(y, dp[(i - 1)&1][j - k * v[i]] + k * w[i]); } dp[i&1][j] = Math.max(n, y); } } return dp[(N - 1)&1][C]; } } 复制代码
- 时间复杂度：共有 N∗CN * CN∗C 个状态需要被转移，但每次转移都需要枚举当前物品的件数，最多枚举 C 次（重量为最小值 1），因此整体复杂度为 O(N∗C∗C)O(N * C * C)O(N∗C∗C)
- 空间复杂度：O(N∗C)O(N * C)O(N∗C)
一维空间优化
我们知道在 01 背包中，最重要的是「一维空间优化」解法。
之所以 01 背包能够使用「一维空间优化」解法，是因为当我们开始处理第 iii 件物品的时候，数组中存储的是已经处理完的第 i−1i - 1i−1 件物品的状态值。
然后配合着我们容量维度「从大到小」的遍历顺序，可以确保我们在更新某个状态时，所需要用到的状态值不会被覆盖。
因此 01 背包问题的状态转移方程为：
dp[j]=max(dp[j],dp[j−v[i]]+w[i])dp[j] = max(dp[j], dp[j - v[i]] + w[i])dp[j]=max(dp[j],dp[j−v[i]]+w[i])
同时容量维度的遍历顺序为从大到小。
PS. 如果你不太理解上面的话，或许是因为你「还没学习」或者「有点忘记」01 背包问题，三叶强烈建议你先对 01 背包问题 进行学习/回顾。
而「完全背包」区别于「01 背包」，在于每件物品可以被选择多次。
因此你可能会在别的地方看到这样的讲解：
「01 背包将容量维度「从大到小」遍历代表每件物品只能选择一件，而完全背包将容量维度「从小到大」遍历代表每件物品可以选择多次。」
这样的解释其实是利用了人的抽象思维，但感觉不一定是对的。
接下来，我们从「数学」的角度去证明为什么修改 01 背包的遍历顺序可以正确求解完全背包问题。
我们先来展开完全背包中 dp[i][j]dp[i][j]dp[i][j] 的所有可能方案：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i],dp[i−1][j−2∗v[i]]+2∗w[i],...,dp[i−1][j−k∗v[i]]+k∗w[i]),0⩽k∗v[i]⩽jdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i],...,dp[i - 1][j - k * v[i]] + k * w[i]), 0\leqslant k*v[i] \leqslant jdp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i],dp[i−1][j−2∗v[i]]+2∗w[i],...,dp[i−1][j−k∗v[i]]+k∗w[i]),0⩽k∗v[i]⩽j
dp[i][j]dp[i][j]dp[i][j] 所代表的含义：在容量允许的情况下，对于第 iii 件物品，我们可以不选，可以选 1 次，可以选 2 次，...，可以选 kkk 次 ...
然后我们通过代入，看看 dp[i][j−v[i]]dp[i][j - v[i]]dp[i][j−v[i]] 是什么内容：
dp[i][j−v[i]]=max(dp[i−1][j−v[i]],dp[i−1][j−2∗v[i]]+w[i],dp[i−1][j−3∗v[i]]+2∗w[i],...,dp[i−1][j−k∗v[i]]+(k−1)∗w[i]),0⩽k∗v[i]⩽jdp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2 * v[i]] + w[i], dp[i - 1][j - 3 * v[i]] + 2 * w[i],...,dp[i - 1][j - k * v[i]] + (k - 1) * w[i]), 0\leqslant k*v[i] \leqslant jdp[i][j−v[i]]=max(dp[i−1][j−v[i]],dp[i−1][j−2∗v[i]]+w[i],dp[i−1][j−3∗v[i]]+2∗w[i],...,dp[i−1][j−k∗v[i]]+(k−1)∗w[i]),0⩽k∗v[i]⩽j
光看公式可能很难看出两者的联系，三叶将相同的部分进行标记：
总结一下。
- 0-1 背包问题的状态转换方程是：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])
由于计算 dp[i][j]dp[i][j]dp[i][j] 的时候，依赖于 dp[i−1][j−v[i]]dp[i - 1][j - v[i]]dp[i−1][j−v[i]]。
因此我们在改为「一维空间优化」时，需要确保 dp[j−v[i]]dp[j - v[i]]dp[j−v[i]] 存储的是上一行的值，即确保 dp[j−v[i]]dp[j - v[i]]dp[j−v[i]] 还没有被更新，所以遍历方向是从大到小。
- 完全背包问题的状态转移方程是：
dp[i][j]=max(dp[i−1][j],dp[i][j−v[i]]+w[i])dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])dp[i][j]=max(dp[i−1][j],dp[i][j−v[i]]+w[i])
由于计算 dp[i][j]dp[i][j]dp[i][j] 的时候，依赖于 dp[i][j−v[i]]dp[i][j - v[i]]dp[i][j−v[i]]。
因此我们在改为「一维空间优化」时，需要确保 dp[j−v[i]]dp[j - v[i]]dp[j−v[i]] 存储的是当前行的值，即确保 dp[j−v[i]]dp[j - v[i]]dp[j−v[i]] 已经被更新，所以遍历方向是从小到大。
代码：
class Solution { public int maxValue(int N, int C, int[] v, int[] w) { int[] dp = new int[C + 1]; for (int i = 0; i < N; i++) { for (int j = 0; j <= C; j++) { // 不考虑第 i 件物品的情况（选择 0 件物品 i） int n = dp[j]; // 考虑第 i 件物品的情况 int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0; dp[j] = Math.max(n, y); } } return dp[C]; } } 复制代码
- 时间复杂度：共有 N∗CN * CN∗C 个状态需要被转移，复杂度为 O(N∗C)O(N * C)O(N∗C)
- 空间复杂度：O(C)O(C)O(C)
总结
今天我们学习了【动态规划/背包问题】中的「完全背包」问题。
形式上，我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。
但本质是因为两者进行状态转移时依赖了不同的格子：
- 01 背包依赖的是「上一行正上方的格子」和「上一行左边的格子」。
- 完全背包依赖的是「上一行正上方的格子」和「本行左边的格子」。
另外，我们可以发现通过「一维空间优化」方式，可以将求解「完全背包」问题的时间复杂度从 O(N∗C∗C)O(N * C * C)O(N∗C∗C) 降低为 O(N∗C)O(N*C)O(N∗C)。
这就是为什么三叶一直强调 01 背包问题的「一维空间优化」解法是几乎所有背包问题的基础。
背包问题（目录）
- 01背包 : 背包问题 第一讲
- 完全背包 : 本篇
- 多重背包 : 背包问题 第八讲
- 多重背包（优化篇）
- 【练习】分组背包 : 背包问题 第十三讲
- 多维背包
- 树形背包 : 背包问题 第十六讲
- 【练习篇】树形背包 : 背包问题 第十七讲
- 【练习篇】树形背包
- 背包求方案数
- 【练习】背包求方案数
- 背包求具体方案
- 【练习】背包求具体方案
- 泛化背包
- 【练习】泛化背包
