问题概述
有一个背包，最大承重为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
如有错误，敬请指正，欢迎交流，谢谢?(･ω･)ﾉ