问题概述完全背包特点完全背包（一维滚动数组版本）
分析代码最后结果 文章目录
问题概述完全背包特点完全背包（一维滚动数组版本）
分析代码最后结果 问题概述
有一个背包，最大承重为N，现在要装一些物品i（物品价值为value[i],物品重量为weight[i]），物品数量不限（即可以重复装），求这个背包装这些物品后的最大价值。
完全背包特点每种物品有无限个
完全背包（一维滚动数组版本） 分析前面的01背包我们可以知道，外面循环物品为正序，内部反向循环背包。内部反向循环是为了保证物品只能被添加一次，但完全背包有无限个物品，说明我的背包可以正向遍历，子问题叠加也没什么。01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序可以颠倒所以，无论是01背包还是完全背包，我们一般都先遍历物品，再遍历背包，注意：这里是一般 代码
# 完全背包（一维滚动数组版本）weight =[1,3,4]value = [15,20,30] Max = 4 # 背包的最大容量dp = [0]*5 # dp[j]表示背包容量为j的最大价值为dp[j]for i in range(3): for j in range(weight[i],5): dp[j] = max(dp[j],dp[j-weight[i]]+value[i])print(dp)
最后结果所以容量为4的背包，最大价值是60
如有错误，敬请指正，欢迎交流，谢谢♪(･ω･)ﾉ