01背包
题目描述
有 N 件物品,放入第 i 件物品的耗费是 w[i],得到的价值是 v[i],现给出一个容量为 C 的背包,每种物品只能选一次(选或者不选),如何选取物品,使得在不超过背包容量C的前提下,让装进去的物品总价值最大。
例题 洛谷1048
基本思路
子问题
dp[i][j]
表示前 i 个物品,放入容量为 j 的背包中可以获得的最大价值。
若只考虑第 i 件物品的策略(放或不放),那么就可以转化为一个只和前 i − 1 件物品相关的问题:
- 如果不放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入容量为 j 的背包中”,价值为
dp[i − 1, j]
; - 如果放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入剩下的容量为
j − w[i]
的背包中”,此时能获得的最大价值就是dp[i-1][j − w[i]]
再加上通过放入第 i 件物品获得的价值v[i]
初始状态
没有物品时,背包的价值一定是0 $$ dp[0][j] = 0 $$
状态转移
1 for (int i = 1; i <= n; ++i) {
2 for (int j = 0; j <= cap; ++j) {
3 if (j < w[i]) // 放不下
4 dp[i][j] = dp[i - 1][j];
5 else
6 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
7 }
8 }
9 return dp[n][cap];
时间复杂度为 $ O(NC) $,其中 N 为物品数量,C 为背包容量。
空间复杂度为 $ O(NC) $,其中 N 为物品数量,C 为背包容量。
空间优化
我们注意到,计算 dp[i][j]
时只需要参考 dp[i-1][...]
,不需要更早的旧值了,这意味着我们可以使用滚动数组进行优化,只需要两个数组,根据 i
和 i-1
的奇偶性不同,轮换保存 dp[i][...]
和 dp[i-1][...]
的状态
1 for (int i = 1; i <= n; ++i) {
2 for (int j = 0; j <= cap; ++j) {
3 if (j < w[i]) // 放不下
4 dp[i % 2][j] = dp[(i - 1) % 2][j];
5 else
6 dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - w[i]] + v[i]);
7 }
8 }
9 return dp[n % 2][cap];
此时空间复杂度为 $ O(C) $,但还可以更进一步,只用一维数组,在上面原地更新。此时我们只需要更新 w[i]
到 cap
部分,但注意,当 cap-w[i] >= w[i]
时,如果按照 w[i]
到 cap
从小到大的顺序更新dp值时,w[i]
会在被作为参考值前被更新覆盖,使得结果出错,因此需要从大到小更新。
1 for (int i = 1; i <= n; ++i) {
2 for (int j = cap; j >= w[i]; --j) {
3 dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
4 }
5 }
6 return dp[cap];
常数优化
如果背包的容量 C 远大于物品的总耗费 $ \sum_{i}^{n} w[i] $,即所有物品都能放进背包时,我们仅需考虑对答案值dp[cap]
产生影响的后半部分 $ C - \sum_{i}^{n} w[i] + 1 $ 的状态更新,
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 |
1 int effective = cap - sumw + 1;
2 for (int i = 1; i <= n; ++i) {
3 for (int j = cap; j >= max(effective, w[i]); --j) {
4 dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
5 }
6 }
7 return dp[cap];