背包问题一： 01 背包

[meishaoming]

问题：

有 5 个不同的物品 a, b, c, d e ，它们的重量分别为 2, 2, 6, 5, 4，它们的价值分别为 6, 3, 5, 4 6。 我有一个背包最大能装下重量 10，从其中拿任意物品到包里，能获得的最大价值是多少？

物品的重量、价值对应表如下：

物品	重量	价值
a	2	6
b	2	3
c	6	5
d	5	4
e	4	6

审题：

1. 对于每个物品只有两种选择：拿 或 不拿，所以称为 0、1 背包问题。
2. 每种物品只有一个。如果每种物品有无限个的话就是「完全背包问题」，如果每种物品有特定数量，则是「多重背包问题」。

用动态规划分析，先把表格画好。表格中的 0..10 这些列表示当背包容量分别是 0, 1, .. 10 时的情况。

假设桌上只有一个物品 a

a 重量为 2，价值为 6。

我手里拿着一个背包，那么：

0. 如果我手里背包容量为 0，那装不下 a，此时最大获利为 0
1. 如果我手里背包容量为 1，还是装不下 a，此时最大获利为 0
2. 如果我手里背包容量为 2，可以装下 a，拿走，此时最大获利为 6
3. 如果我手里背包容量为 3，可以装下 a，拿走，此时最大获利为 6 。装下 a 之后还剩容量 1，但桌上已没东西可装。 ...
4. 4. 如果我手里背包容量为 10，可以装下 a，拿走，此时最大获利为 6 。装下 a 之后还剩容量 8，但桌上已没东西可装

用以上情况填完表格如下：

假设桌上有两个物品：a, b

a 重量为 2，价值为 6 b 重量为 2，价值为 3

那么：

0. 如果我手里背包容量为 0，那什么也装不下，此时最大获利为 0
1. 如果我手里背包容量为 1，还是什么也装不下，此时最大获利为 0
2. 如果我手里背包容量为 2，这个时候可以拿 a，也可以拿 b ，但没办法两个都拿。如果此时不拿 b ，那就只剩 a 了，只有 a 时的最大获利为 6；如果拿 b，获利 3 ，背包剩余空间为 0，桌面剩下物品 a，那就是上一行的第 0 列时的情况（桌面只有 a，背包空间为 0），即 dp[i-1][0]，。max{6, 3}，最终选择拿 a，此时最大获利 6 。绘图如下：

3. 如果我手里背包容量为 3，如果不拿 b，最大获利 6；如果拿 b，获利 3，剩余空间 1，还是拿不了 a
4. 如果我手里背包容量为 4，如果不拿 b，最大获利 6；如果拿 b，获利 3，剩余空间 2，还可以装下 a 。那 a，b 都拿走，此时最大获利为 9

...

10. 4. 如果我手里背包容量为 10，a，b 都拿走，装下 a，b 之后还剩容量 6，但桌上已没东西可装。此时最大获利为 9 。

填完表格：

填完所有表格

推导公式

dp[i][j] = max{ dp[i-1][j], dp[i-1][j-w[i]] + v[i] }

• i 表示桌上物品个数，（依次排放，取值有 a, ab, abc, abcd, abcde ）
• j 表示当前背包容量。

def knapsack(weights, values, W):
    n = len(weights)
    dp = [ [0] * (W+1) for _ in range(n) ]
    for i in range(0, n):
        for j in range(W+1):
            if i == 0:
                if j < weights[i]:
                    dp[i][j] = 0
                else:
                    dp[i][j] = values[i]
            else:
                if j < weights[i]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], values[i] + dp[i-1][j-weights[i]])
        print(f"{i}: {dp[i]}")
    return dp[-1][-1]

w = [2, 2, 6, 5, 4]
v = [6, 3, 5, 4, 6]

max_value = knapsack(w, v, 10)
print('-------------')
print('max value', max_value)

执行输出的结果：

0: [0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6]
1: [0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9]
2: [0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14]
3: [0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14]
4: [0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]
-------------
max value 15

如果在物品的最开头添加一个物品 0 （重量为 0，价值为 0），就不需要单独处理第一行了：

def knapsack(weights, values, W):
    weights = [0] + weights
    values = [0] + values
    n = len(weights)
    dp = [ [0] * (W+1) for _ in range(n) ]
    for i in range(1, n):
        for j in range(W+1):
            if j < weights[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], values[i] + dp[i-1][j-weights[i]])

    for i in range(n):
        print(f"{i}: {dp[i]}")
    return dp[-1][-1]

w = [2, 2, 6, 5, 4]
v = [6, 3, 5, 4, 6]

max_value = knapsack(w, v, 10)
print('-------------')
print('max value', max_value)

结果为：

0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1: [0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6]
2: [0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9]
3: [0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14]
4: [0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14]
5: [0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]
-------------
max value 15

上边整个算法的时间复杂度为 O(nW) （n 为 物品个数，W 为背包容量）。空间复杂度也为 O(nW)。

优化空间

无论是观察推导公式 dp[i][j] = max{ dp[i-1][j], dp[i-1][j-w[i]] + v[i] }，还是观察图表，我们发现：

计算第 i 行的 dp[] 值时，只需要 i-1 行的数据。我们不需要存下整个二维表格，只需要存下一个一维数组就行了，数组的大小为 W+1。

推导公式变为

dp[j] = max(dp[j], values[i] + dp[j-weights[i]])

注意哈，公式等号的左边 dp[j] 是新的一行的元素，而等号右边 dp[j] 是上一行的元素。

再回想我们填表格时的顺序，每一行都是从左往右填。而对于一维数组，更新右变的值会需要左边的「上一行」的值，如果我们还从左往右更新就不对了。所以需要从右往左更新，也就是从背包容量 10 往容量 0 更新。

而从右往左更新的同时，如果当前背包容量 j 等于物品重量 w[j]，刚好可以装下这个物品。再往左边就肯定装不下这个物品了，所以再左边的数据都不必更新、延用上一轮的数据就好了。

def knapsack1(weights, values, W):
    n = len(weights)
    dp = [0] * (W+1)
    for i in range(0, n):
        for j in range(W, weights[i]-1, -1):
            dp[j] = max(dp[j], values[i] + dp[j-weights[i]])
        print(f"{i}: {dp}")
    return dp[-1]

w = [2, 2, 6, 5, 4]
v = [6, 3, 5, 4, 6]

max_value = knapsack1(w, v, 10)
print('-------------')
print('max value', max_value)

输出为：

0: [0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6]
1: [0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9]
2: [0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14]
3: [0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14]
4: [0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]
-------------
max value 15

其它衍生问题

1. 恰好装满
2. 求和方案总数
3. 所有方案

494. 目标和 416. 分割等和子集 322. 零钱兑换