leetcode动态规划（十五）-完全背包

题目

leetcode上没有纯完全背包题目，可以看卡码网上的题目

完全背包

思路

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

在0-1背包中的遍历顺序为

for i in range(n):for j in range(bagweight,weight[i]-1,-1):dp[j] = max(dp[j],dp[j-weight[i]]+value[i])

在进行背包遍历的时候你从大到小来遍历的，但在完全背包这里每个物品的数量是无限的，那就可以从小到大来进行遍历了，这样在遍历的过程中就会把同一个物品重复装入包中，直到下个物品的价值放到包里超过一直这样放的时候就结束

代码

n , target = 4,5
weight = [1,2,3,4]
value = [2,4,4,5]dp =[0]*(target+1)for i in range(n):for j in range(weight[i],target+1):dp[j] = max(dp[j],dp[j-weight[i]]+value[i])print(dp[-1])