day44 动态规划part6 代码随想录算法训练营 完全背包理论
题目：完全背包理论
我的感悟：
- 记忆中理解。
理解难点：
- 为什么正序就是用多次？
- 因为正序是借用本层左侧的状态，倒序是借用上一层的状态。
演示：
打印DP：
示例代码：
查看代码
# 01背包
def test_CompletePack1(weight, value, bagWeight):
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(f"01背包的dp:{dp}")
return dp[bagWeight]
# 完全背包
def test_CompletePack2(weight, value, bagWeight):
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(weight[i], bagWeight + 1): # 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(f"完全背包的dp:{dp}")
return dp[bagWeight]
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
bagWeight = 4
result1 = test_CompletePack1(weight, value, bagWeight)
result2 = test_CompletePack2(weight, value, bagWeight)
print("01背包的结果:", result1)
print("完全背包的结果:", result2)扩展写法：
资料：
完全背包
视频讲解：https://www.bilibili.com/video/BV1uK411o7c9
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html