0-1背包

发表于 更新于 分类于 ， ，

简介

0-1背包问题：给定n种物品和一背包。每种物品有着重量和价值两个属性，背包的有总容量限制。问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？背包问题有很多种，0-1背包是最为基础的一种，其核心思想均为用动态规划来解决。

解法

设有以下几种物品：

物品(i) 重量(\(w_i\)) 价值(\(v_i\))
物品0 1 2
物品1 2 3
物品2 3 4
物品3 4 5
物品4 5 6

背包总容量(\(w_a\)​)为8，如何选择物品才能让背包的能够装的价值最大？

通常解法

我们用\(dp[i][j]\)​​​​​来表示仅从前i个物品里面选择且总容量为j时的物品的最大价值。动态转移方程可以写成如下形式：

\(dp[i][j] = max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])\)​

每遍历到一个物品的时候，这个物品有装或者不装两种选择，如果装这个物品，则装之后的最大价值为当前物品的价值加上不装之前(容量为\(j-w[i]\)​​​)​​的最大价值，如果不装，则最大价值为前i-1个物品的最大价值，这两者取最大值即可。示例源码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
w = list(range(1, 6))  # 每个物品重量
v = list(range(2, 7))  # 每个物品价值

w_a = 8  # 背包容量

dp = [[0] * (w_a + 1) for _ in range(5)]  # 初始化动态规划数组

for i in range(w_a + 1):  # 初始化边界条件
    if i >= w[0]:
        dp[0][i] = v[0]

for i in range(1, 5):  # 状态转移
    for j in range(1, w_a + 1):
        dp[i][j] = dp[i - 1][j]
        if j - w[i] >= 0:
            dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])

# 最终结果
print(dp[-1][w_a])

11
选择物品134或125的组合可以获得最大价值。
  • dp转移情况:
1
2
3
4
5
[0, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 2, 3, 5, 5, 5, 5, 5, 5]
[0, 2, 3, 5, 6, 7, 9, 9, 9]
[0, 2, 3, 5, 6, 7, 9, 10, 11]
[0, 2, 3, 5, 6, 7, 9, 10, 11]

空间优化

在第二层遍历时\(j\)的状态由\(j\)之前的状态来决定，而\(j\)​不会影响到它之前的状态，因此可以用一维数组存储变量，然后倒序更改此数组，将空间复杂度优化到\(O(w_a)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
w = list(range(1, 6))  # 每个物品重量
v = list(range(2, 7))  # 每个物品价值

w_a = 8  # 背包容量
n = len(w)

dp = [0] * (w_a + 1)  # 初始化动态规划数组

for i in range(w_a + 1):  # 初始化边界条件
    if i >= w[0]:
        dp[i] = v[0]

for i in range(1, n):  # 状态转移
    for j in range(w_a, -1, -1):
        if j - w[i] >= 0:
            dp[j] = max(dp[j - w[i]] + v[i], dp[j])
# 最终结果
print(dp[-1])
11

[0, 2, 3, 5, 6, 7, 9, 10, 11]

END

其他背包问题