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
选择物品134125的组合可以获得最大价值。
  • 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

其他背包问题