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][...],不需要更早的旧值了,这意味着我们可以使用滚动数组进行优化,只需要两个数组,根据 ii-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]会在被作为参考值前被更新覆盖,使得结果出错,因此需要从大到小更新。

01背包空间优化

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];