今天是我们讲解「动态规划专题」中的 「背包问题」的第四天。
在众多背包问题中「01 背包问题」是最为核心的,因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。
其中 01 背包的「一维空间优化」更是要重点掌握。
另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。
你也先可以尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 DP 类型题目 ~
有
种物品和一个容量为
的背包,每种物品都有无限件。
第
件物品的体积是
,价值是
。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
其实就是在 0-1 背包问题的基础上,增加了每件物品可以选择多次的特点(在容量允许的情况下)。
示例 1:
输入: N = 2, C = 5, v = [1,2], w = [1,2]
输出: 5
解释: 选一件物品 1,再选两件物品 2,可使价值最大。
我们可以直接将 01 背包的「状态定义」拿过来用:
代表考虑前
件物品,放入一个容量为
的背包可以获得的最大价值。
由于每件物品可以被选择多次,因此对于某个
而言,其值应该为以下所有可能方案中的最大值:
的最大价值,即
的最大价值,即
的最大价值,即
...
的最大价值,
由此我们可以得出「状态转移方程」为:
代码:
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];
}
}
个状态需要被转移,但每次转移都需要枚举当前物品的件数,最多枚举 C 次(重量为最小值 1),因此整体复杂度为
通过观察我们的「状态转移方程」可以发现,我们在更新某个
的时候只依赖于
。
因此我们可以像 01 背包那样使用「滚动数组」的方式将空间优化到
。
代码:
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];
}
}
个状态需要被转移,但每次转移都需要枚举当前物品的件数,最多枚举 C 次(重量为最小值 1),因此整体复杂度为
我们知道在 01 背包中,最重要的是「一维空间优化」解法。
之所以 01 背包能够使用「一维空间优化」解法,是因为当我们开始处理第
件物品的时候,数组中存储的是已经处理完的第
件物品的状态值。
然后配合着我们容量维度「从大到小」的遍历顺序,可以确保我们在更新某个状态时,所需要用到的状态值不会被覆盖。
因此 01 背包问题的状态转移方程为:
同时容量维度的遍历顺序为从大到小。
PS. 如果你不太理解上面的话,或许是因为你「还没学习」或者「有点忘记」01 背包问题,三叶强烈建议你先对 01 背包问题 进行学习/回顾。
而「完全背包」区别于「01 背包」,在于每件物品可以被选择多次。
因此你可能会在别的地方看到这样的讲解:
「01 背包将容量维度「从大到小」遍历代表每件物品只能选择一件,而完全背包将容量维度「从小到大」遍历代表每件物品可以选择多次。」
这样的解释其实是利用了人的抽象思维,但感觉不一定是对的。
接下来,我们从「数学」的角度去证明为什么修改 01 背包的遍历顺序可以正确求解完全背包问题。
我们先来展开完全背包中
的所有可能方案:
所代表的含义:在容量允许的情况下,对于第
件物品,我们可以不选,可以选 1 次,可以选 2 次,...,可以选
次 ...
然后我们通过代入,看看
是什么内容:
光看公式可能很难看出两者的联系,三叶将相同的部分进行标记:
总结一下。
由于计算
的时候,依赖于
。
因此我们在改为「一维空间优化」时,需要确保
存储的是上一行的值,即确保
还没有被更新,所以遍历方向是从大到小。
由于计算
的时候,依赖于
。
因此我们在改为「一维空间优化」时,需要确保
存储的是当前行的值,即确保
已经被更新,所以遍历方向是从小到大。
代码:
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];
}
}
个状态需要被转移,复杂度为
今天我们学习了【动态规划/背包问题】中的「完全背包」问题。
形式上,我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。
但本质是因为两者进行状态转移时依赖了不同的格子:
另外,我们可以发现通过「一维空间优化」方式,可以将求解「完全背包」问题的时间复杂度从
降低为
。
这就是为什么三叶一直强调 01 背包问题的「一维空间优化」解法是几乎所有背包问题的基础。
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。