[TOC] # 01背包 ## 问题及背景 今天是蛋糕店开的第二天啦，蛋糕店的老板昨天在关门查帐的时候发现，剩下了很多不完整的蛋糕，可能是因为谁都不想拿被别人掰过的蛋糕吧😥。 为了不浪费食物，老板在昨天规则的基础上做了一点修改：**不再允许掰蛋糕**。 因此对于一块蛋糕你只能选择要或者不要。注意每种蛋糕只有一个哦。 请问今天你该怎么拿蛋糕呢？ 这就是经典的01背包问题了，还是那个背包，还是那些各不相同的蛋糕，不同的是你只能选择`拿(1)`或者`不拿(0)`。 ## 分析 这个问题看上去好像可以用部分背包的方法来做。 但是我们考虑这样一个例子： 背包容量为 5 有三种不同的蛋糕，规格如下： | 体积 | 价值 | | --- | --- | | 4 | 10 | | 2 | 4 | | 3 | 7 | 如果按照”贪心“的选取”性价比“更高的蛋糕的话，就会选择只第一块蛋糕。 但是，显然我们选择第二块和第三块可以得到更高的价值。 所以我们必须考虑其他方法。 ## 动态规划解法 以[51NOD-1085](http://www.51nod.com/Challenge/Problem.html#!#problemId=1085)为例。 因为似乎找不到什么排序方式可以保证按照该方式排序后，依次选取蛋糕就可以获得最大值，所以没有必要再进行排序。 可以发现背包的容积是固定且已知的，所以考虑从背包的容积入手。 定义`f[i][j]`表示我们只能选择前`i`个物品，背包的容积为`j`时，可以得到的最大价值。当我们在选择第`i`种物品时，我们可以通过枚举背包的容积`j`来不断更新`f[i][j]`的最大值。 图示：  1. 状态：`f[i][j]`表示选择前`i`个物品，背包容积为`j`时最大价值。 2. 转移方程：`f[i+1][j] = max(f[i][j], f[i][j-cost[i]]+va[i])` 3. 初始化：全部初始化为0。 4. 答案：`f[n][v]` ### 复杂度和代码 时间复杂度：O(n\*v) 空间复杂度：O(n\*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 j in range(v+1)] for i in range(n+1)] for i in range(n): for j in range(v+1): if j < cost[i]: dp[i+1][j] = dp[i][j] else: dp[i+1][j] = max(dp[i][j], dp[i][j-cost[i]] + val[i]) print(dp[n][v]) ~~~ ## 优化 在上面的动态规划中，可以发现dp函数的第一维好像不是那么重要，因此我们想知道我们能不能把第一维去掉，这样能够节省很多内存。 定义`f[j]`表示背包大小为`j`时可以获得的最大价值。 然后同样枚举物品和背包容量，不过循环的内容有些不同，详细见代码注释。 ### 复杂度和代码 时间复杂度：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(v, cost[i]-1, -1): ''' 首先，j>=cost[i]，不然这个背包装不下这个物品。 另外，需要注意我们枚举j是从大到小的，这点尤其重要。 这个顺序可以保证我们每一个物品都只取一次。 ''' dp[j] = max(dp[j], dp[j-cost[i]]+val[i]) print(dp[v]) ~~~