细说背包问题 - 完全背包
分类
背包模型的本质,就是从 n 种物品种选择若干,放入容量为 m 的背包。按照每种物品的数量,背包问题可以分成以下三种基本类型:
01背包
:每种物品只有 1 件,可以选择 0 件,可以选择 1 件完全背包
:每种物品数量无限,可以选择 0 件,可以选择 1 件,可以选择 2 件…只要已选物品的总重量不超过背包容量多重背包
:每种物品数量有限,可以选择 0 件,可以选择 1 件,可以选择 2 件…只要不超过该种物品的数量,且已选物品的总重量不超过背包容量
完全背包
解题
- 约定用
f[i][j]
表示从前 i 种物品中选择若干,放入容量为 j 的背包所能够获得的最大总价值,分别用 w 和 v 表示第 i 种物品的重量和价值
- 若选择 0 件第 i 种物品,等价于先从前 i - 1 种物品中选择若干,放入容量为 j 的背包,获得的最大总价值为
f[i - 1][j]
- 若选择 1 件第 i 种物品,等价于先从前 i - 1 种物品中选择若干,放入容量为 j - w 的背包,获得的最大总价值为
f[i - 1][j - w] + v
- 若选择 2 件第 i 种物品,等价于先从前 i - 1 种物品中选择若干,放入容量为 j - 2 * w 的背包,获得的最大总价值为
f[i - 1][j - 2 * w] + 2 * v
- 。。。。。。
- 若选择 3 件第 i 种物品,等价于先从前 i - 1 种物品中选择若干,放入容量为 j - 3 * w 的背包,获得的最大总价值为
f[i - 1][j - 3 * w] + 3 * v
- 用变量来表示,若选择 k 件第 i 种物品,等价于先从前 i - 1 种物品中选择若干,放入容量为 j - k * w 的背包,获得的最大总价值为
f[i - 1][j - k * w] + k * v
,k的值满足0 <= k <= j / w
- 我们通过打擂台,找到从前 i 种物品中选择若干,放入容量为 j 的背包所能够获得的最大总价值
- 题目要求的,从前 n 种物品中选择若干,放入容量为 m 的背包,能够获得的最大总价值,即
f[n][m]
代码如下:
#include using namespace std;int m, n;int f[39][209];int main() {cin >> m >> n;for (int i = 1; i <= n; i ++) {int w, v;cin >> w >> v;for (int j = 1; j <= m; j ++) {for (int k = 0; k <= j / w; k ++) {f[i][j] = max(f[i][j], f[i - 1][j - k * w] + k * v);}}}cout << "max=" << f[n][m];return 0;}
优化时间复杂度
这个代码无论时间复杂度还是空间复杂度,都不是最优的。我们进一步观察状态转移方程。
- 分别用 w 和 v 表示第 i 种物品的重量和价值,如果背包容量
j >= w
,我们考虑以下两种情况:
- 从前 i 种物品中选择若干,放入容量为 j 的背包,从下表左侧这一列中找出的最大值就是
f[i][j]
- 从前 i 种物品中选择若干,放入容量为 j - w 的背包,从下表右侧这一列中找出的最大值就是
f[i][j - w]
前 i 种物品 -> 容量为 j 的背包 | 前 i 种物品 -> 容量为 j - w 的背包 | 左右两列相差 |
---|---|---|
f[i - 1][j] (选0件) |
不适用 | |
f[i - 1][j - 1 * w] + 1 * v (选1件) |
f[i - 1][j - 1 * w] (选0件) |
v |
f[i - 1][j - 2 * w] + 2 * v (选2件) |
f[i - 1][j - 2 * w] + 1 * v (选1件) |
v |
f[i - 1][j - 3 * w] + 3 * v (选3件) |
f[i - 1][j - 3 * w] + 2 * v (选2件) |
v |
。。。。。。 | 。。。。。。 |
- 对比这两列,我们得出
f[i][j] = max(f[i - 1][j], f[i][j - w] + v
- 这个新的状态转移方程中不再出现变量 k,也就是说,我们可以用嵌套循环取代三重循环!
- 如果背包容量
j < w
,则f[i][j] = f[i - 1][j]
代码如下:
#include using namespace std;int m, n;int f[39][209];int main() {cin >> m >> n;for (int i = 1; i <= n; i ++) {int w, v;cin >> w >> v;for (int j = 1; j <= m; j ++) {if (j < w) f[i][j] = f[i - 1][j];else f[i][j] = max(f[i - 1][j], f[i][j - w] + v);}}cout << "max=" << f[n][m];return 0;}
优化空间复杂度
- 上面的代码使用二维数组,
f[i][j]
表示从前 i 种物品中选择若干,放入容量为 j 的背包能够获得的最大总价值。 - 和处理01背包的方法一样,我们可以将二维数组 f 压缩成一维数组
f[i][j] = max(f[i - 1][j], f[i][j - w] + v)
变成f[j] = max(f[j],f[j - w] + v
f[i][j] = f[i - 1][j]
变成f[j] = f[j]
,这条语句可以省略- 这样一来,完全背包和01背包的状态转移方程变得一模一样。整个代码的区别在于,01背包的第二重循环,是从大到小枚举背包容量,而完全背包的第二重循环,是从小到大枚举背包容量。
- 我们从这个角度来理解,假设有一个容量为 j 的背包,它装载物品的最大价值是
f[j]
。如果增加一件重量为 w 的物品后不会超过容量 m,则容量为 j + w的背包的最大价值f[j + w] = f[j] + v
;如果再增加一件重量为 w 的物品不会超过容量 m,则容量为 j + 2 * w 的背包的最大价值f[j + 2 * w] = f[j + w] + v
,…。当我们从小到大枚举背包容量的时候,恰好对应多次选择同一种物品。
f[j + w] = f[j] + v
,选择 1 次
f[j + 2 * w] = f[j + w] + v
,选择 2 次
f[j + 3 * w] = f[j + 2 * w] + v
,选择 3 次
f[j + 4 * w] = f[j + 3 * w] + v
,选择 4 次
。。。。。。
代码如下
#include using namespace std;int m, n;int f[209];int main() {cin >> m >> n;for (int i = 1; i <= n; i ++) {int w, v;cin >> w >> v;for (int j = w; j <= m; j ++) {f[j] = max(f[j], f[j - w] + v);}}cout << "max=" << f[m];return 0;}