动态规划 | 完全背包问题笔记 | 代码随想录

跟随carl代码随想录刷题
语言：python

---

完全背包

⭐️每种物品都有无数件。

⭐️遍历顺序：

• 01背包的内循环是从大到小遍历的
  • 再次强调：
    • 01背包中二维dp数组的两个for遍历的先后顺序可以颠倒。
    • 一维dp数组的两个for循环先后顺序必须是先遍历物品，再遍历背包容量。
• 而完全背包的内循环是从小到大遍历的
  • 纯完全背包的一维dp数组两个for循环的嵌套顺序不重要。
    • 因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

先遍历物品，再遍历背包

def test_complete_pack1():
	weight = [1, 3, 4]
	value = [15, 20, 30]
	bag_weight = 4

	# 初始化
	dp = [0] * (bag_weight + 1)
	
	# 先遍历物品
	for i in range(len(weight)):
		# 再遍历背包
		for j in range(weight[i], bag_weight + 1):
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	print(dp[bag_weight])
1
2
3
4
5
6
7
8
9
10
11
12
13
14

先遍历背包，再遍历物品

def test_complete_pack2():
	weight = [1, 3, 4]
	value = [15, 20, 30]
	bag_weight = 4

	# 初始化
	dp = [0] * (bag_weight + 1)
	
	# 先遍历背包
	for j in range(bag_weight + 1):
		# 再遍历物品
		for i in range(len(weight)):
			if j >= weight[i]:
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	print(dp[bag_weight])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15