python 背包问题 动态规划

问题分析子问题界定：由参数 k 和 y 界定k：考虑对物品1, 2, … , k 的选择
y：背包总重量不超过 y
原始输入：k = n, y = b
子问题计算顺序： k = 1, 2, … , n
对于给定的 k，y = 1, 2, … , b
定义问题
假设有 n 个物品和一个最大承重为 W 的背包。每个物品 𝑖i 有一定的重量 wi 和价值 vi。我们的目标是选择一些物品装入背包，使得总重量不超过 W，且总价值最大。
动态规划数组定义
定义一个二维数组 dp，其中 dp[i][j] 表示从前 𝑖i 个物品中选取一些，使得总重量不超过 j 时的最大价值。
初始条件
初始化 𝑑𝑝[0][𝑗]=0对所有 j 成立，因为没有物品时，无论背包容量如何，可装入的最大价值都是 0。

转移方程
对于每个物品 i 和每种背包容量 j：
如果不选择物品 i：则 dp[i][j]=dp[i−1][j]
如果选择物品 i（前提是 𝑗≥𝑤i）：则 dp[i][j]=max(dp[i−1][j],dp[i−1][j−wi]+vi)
dp[i][j]=max(dp[i−1][j],dp[i−1][j−wi]+vi)
这个方程的含义可以这样理解：

1. dp[i−1][j]: 这部分表示如果我们不选择当前的物品 i，则问题就退化为“从前i−1 个物品中选择，背包容量为 j 的情况”。在这种情况下，我们已经在上一个状态计算出了不包括物品 i 时的最大价值。
2. dp[i−1][j−wi]+vi: 这部分表示如果我们选择了当前的物品 i，则背包剩余的容量将减少 wi（物品 i 的重量），因此我们需要考虑的子问题变为“从前 i−1 个物品中选择，背包容量为 j−wi 的情况”。由于我们选择了物品 i，我们必须在此基础上加上物品 i 的价值 vi。

def knapsack(n, b, v, w):
	'''
	:param n: 物品有n种
	:param b: 背包容量
	:param v: 物品价值
	:param w: 物品重量
	:return: 最大价值
	'''
	# 初始化
	V = [[0 for _ in range(b + 1)] for _ in range(n + 1)]  # V[i][j] 表示前i个物品放入容量为j的背包的最大价值
	for i in range(n + 1):  # 应该到n+1，包含所有物品
		for j in range(b + 1):  # 应该到b+1，包含背包的完整容量
			if i == 0 or j == 0:  # 初始化 当i=0或j=0时，表示前i个物品放入容量为j的背包的最大价值为0
				V[i][j] = 0
			elif j < w[i - 1]:  # 注意这里的索引应该是i-1，因为列表是从0开始 表示前i个物品放入容量为j的背包的最大价值为前i-1个物品放入容量为j的背包的最大价值
				V[i][j] = V[i - 1][j]
			else:  # 当j>=w[i-1]时，选择放入物品i或不放入
				V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i - 1]] + v[i - 1])
	# 回溯部分
	solution = []
	i, j = n, b
	while i > 0 and j > 0:
		if V[i][j] != V[i - 1][j]:  # 如果选择了物品i
			solution.append(i - 1)  # 添加物品i到解决方案 列表中 因为索引从0开始 所以要减1
			j -= w[i - 1]  # 更新剩余背包容量
			i -= 1  # 更新物品索引
		else:  # 如果V[i][j]等于V[i - 1][j]，这意味着第i个物品没有被选中，因为不考虑这个物品我们可以得到相同的最大价值。因此，只需要简单地将物品索引i减1，继续考虑下一个物品。
			i -= 1
	
	# 返回最大价值和选择的物品列表
	return V[n][b], [v[i] for i in reversed(solution)]


if __name__ == '__main__':
	n = 4
	b = 10
	v = [1, 3, 5, 9]
	w = [2, 3, 4, 7]
	max_value, solution = knapsack(n, b, v, w)
	print(f"最大价值为: {max_value}")
	print(f"选择的物品: {solution}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

回溯部分从V[n][b]开始，通过比较当前状态V[i][j]和V[i - 1][j]来判断是否将第i个物品放入背包中。如果当前状态的价值不是由前一个物品的价值转移而来，说明第i个物品没有被选中；否则，第i个物品被选中，更新背包容量j并继续回溯。
4. 在循环体内，首先检查V[i][j]和V[i - 1][j]的值。这两个值的含义如下：
○ V[i][j]：考虑前i个物品，背包容量为j时的最大价值。
○ V[i - 1][j]：考虑前i - 1个物品，背包容量为j时的最大价值。
5. 如果V[i][j]不等于V[i - 1][j]，这意味着在将第i个物品放入背包时，我们得到了更高的价值。因此，执行以下操作：
○ 将物品i - 1（因为数组是从0开始索引的）添加到解决方案列表solution中。
○ 从剩余背包容量j中减去物品i - 1的重量w[i - 1]，因为背包中加入了这个物品。
○ 将物品索引i减1，继续考虑下一个物品。
6. 如果V[i][j]等于V[i - 1][j]，这意味着第i个物品没有被选中，因为不考虑这个物品我们可以得到相同的最大价值。因此，只需要简单地将物品索引i减1，继续考虑下一个物品。