一文搞懂背包问题

发表于 更新于 分类于

难乎？甚难。有何难哉？亦不难。

动态规划套路

所有的背包问题都是动态规划。动态规划，一定要明确 「状态」 和 「选择」 ，明确了之后，所有的动态规划都可以套在下面公式中：

1
2
3
4
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 择优(选择1, 选择2, ...)

0-1背包问题

问题描述

给你一个可装载重量为 W 的背包，和 N 个物品。每个物品有重量和价值两个属性，第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

解

首先找到状态，有两个，一个是可选的物品，一个是背包的容量，那么我们可以定义状态转移方程：

dp[i][w]: 对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。

根据此定义，我们想求的最终答案是 dp[N][W]，base case 就是 dp[0][..,] = dp[…][0] = 0，因为没有物品或背包的时候，最大价值就是0。

细化上面的框架：

1
2
3
4
5
6
7
8
9
10
11
12
int dp[N + 1][W + 1];
dp[0][...] = 0;
dp[...][0] = 0;

for i in [1...N]:
    for w in [1...W]:
            dp[i][w] = max(
                把物品 i 装进背包,
                不把物品 i 装进背包,
            );

return dp[N][W];

之后就是选择，如何选择呢，如何在代码中体现这两种选择呢？

还是需要重申一下对 dp 的定义，**dp[i][w]: 对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。**。

  1. 如果没有把第 i 个物品装入背包，那么 dp[i][w] 应该等于 dp[i-1][w]， 不装嘛，就是继承之前的结果。
  2. 如果把第 i 个物品装入背包了，那么 dp[i][w] 应该等于 dp[i-1][w - wt[i - 1]] + val[i - 1]，（因为 i 是从 1 开始的）。如何理解dp[i-1][w - wt[i - 1]]呢，因为我们需要把第 i 个物品放入背包，需要占用 wt[i - 1] 的重量，所以我们要寻找剩余重量限制下w - wt[i-1] 能装的最大价值。

基于以上两种情况，我们就可以翻译出代码了，再加上处理一些边界情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int knapsack(int W, int N, int[] wt, int[] val) {
    int[][] dp = new int[val.length + 1][wt.length + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] > w) {
                // 当前背包背不下
                dp[i][w] = dp[i - 1][w];
            } else {
                // 背包可以背下，选择不背或背的最优质的
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][wt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[N][W];
}

完全背包问题

问题描述

这个问题和01背包问题比较相似，唯一的区别就是每种物品都有无数件。从每种物品的角度考虑，与之有关的策略不再是「取」或「不取」两种状态，而是取0件、取1件、…取N件。

解

这题的状态转移方程和之前的一样：

有两个状态，一个是可选的物品，一个是背包的容量，那么我们可以定义状态转移方程：

dp[i][w]: 对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。

1
2
3
4
5
6
7
8
9
10
11
12
int dp[N + 1][W + 1];
dp[0][...] = 0;
dp[...][0] = 0;

for i in [1...N]:
    for w in [1...W]:
            dp[i][w] = max(
                把物品 i 装进背包,
                不把物品 i 装进背包,
            );

return dp[N][W];

那么就是如何用代码描述这两种选择了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int knapsack(int W, int N, int[] wt, int[] val) {
    int[][] dp = new int[val.length + 1][wt.length + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] > w) {
                // 当前背包背不下
                dp[i][w] = dp[i - 1][w];
            } else {
                // 背包可以背下，选择不背或背的最优质的
                dp[i][w] = Math.max(dp[i - 1][w], dp[i][wt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[N][W];
}

这两者代码区别非常微小。因为完全背包物品有无限个，所以是 dp[i][wt[i - 1]] + val[i - 1] 而不是 dp[i - 1][wt[i - 1]] + val[i - 1]，可以再继续拿。

背包变体

1049. 最后一块石头的重量 II