[TOC] # 完全背包 ## 问题及背景 今天是蛋糕店开张第三天啦💕，也是活动的最后一天了，老板决定加大活动力度，**每种蛋糕不限量**！！，也就是说在上一节的01背包中我们每一种蛋糕最多只能拿一个，但是今天你可以任意拿(只要你的背包能放的下)。 ## 分析 首先可以知道，虽然说蛋糕不限量，但是背包的大小是一定的，对于每一种蛋糕可以算出一个最大能装下的数量`max[i]`，然后从0到`max[i]`枚举数量就可以了。 这样做的时间复杂度是O(n\*v\^2)，这是不能接受的。 更换思路，在上一节01背包中我们提到过，枚举背包容量`j`时，我们要从大到小枚举，那么我们如果从小到大枚举会发生什么呢？ 没错，恰恰就是完全背包的枚举方式。 可以归纳性证明： 当枚举到`cost[i]`时，方程会更新拿一个`i`个物品，判断最大价值会不会更大。在枚举到`2*cost[i]`时，方程会更新再拿一个`i`物品，判断最大价值会不会更大，因为之前更新了拿一个`i`物品的状态，所以此次拿是第2个，以此类推。。。 ### 复杂度和代码 时间复杂度：O(n*v) 空间复杂度：O(v) 代码如下： ~~~py n, v = map(int, input().split()) cost = [0 for i in range(n)] val = [0 for i in range(n)] for i in range(n): c, vl = map(int, input().split()) cost[i], val[i] = c, vl dp = [0 for i in range(v+1)] for i in range(n): for j in range(cost[i], v + 1): ''' 首先，j>=cost[i]，不然这个背包装不下这个物品。 另外，需要注意我们枚举j是从小到大的，这点尤其重要。 这个顺序可以保证我们每一个物品可取任意次。 ''' dp[j] = max(dp[j], dp[j-cost[i]]+val[i]) print(dp[v]) ~~~