01背包问题-空间复杂度o(V)

**题目** 有N件物品和一个容量为V的背包。第i件物品的所需容量是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

---

f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。 现在我们来看第ｉ件物品： －－－如果选择将第ｉ件物品放入，那么在放置前ｉ－１件物品的时候应该空出ｖ-ｃ[i]的容量，此时方程为ｆ[i-1][v-c[i]]+w[i] －－－如果选择不将第ｉ件物品放入，那么此时的最大价值前第ｉ-1件放入容量为ｖ的背包获得的最大价值决定，此时方程为f[i-1][v] 综上所述，得出ｆ[i][v]

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

---

推荐大家走一遍实例，看一下下方结果输出的表格，表格懂了，算法就懂了 假设当前有五件商品（重量，价值）（5，12），（4，3），（7，10），（2，3），（6，6） 背包容量为１５ 解决代码如下所示 时间复杂度以及空间复杂度均为ｏ（Ｎ×Ｖ）

#coding=utf-8 class Solution(): def zero_one(self,goods,max_V): f = [[0] * (max_V+1) for i in range(len(goods))] for v in range(goods[0][0],max_V+1): f[0][v] = goods[0][1] for i in range(1,len(goods)): for v in range(max_V+1): #注意下面ｉｆ语句判断，如果ｖ<当前商品质量，那么ｆ[i][v]就是f[i-1][v] if v>=goods[i][0]: f[i][v] = max(f[i-1][v],f[i-1][v-goods[i][0]]+goods[i][1]) else: f[i][v] = f[i-1][v] return f goods = [[5,12],[4,3],[7,10],[2,3],[6,6]] test = Solution() PRint test.zero_one(goods,15)

前ｎ件商品	０	１	２	３	４	５	６	７	８	９	１０	１１	１２	１３	１４	１５
1	0	0	0	0	0	12	12	12	12	12	12	12	12	12	12	12
2	0	0	0	0	3	12	12	12	12	15	15	15	15	15	15	15
3	0	0	0	0	3	12	12	12	12	15	15	15	22	22	22	22
4	0	0	3	3	3	12	12	15	15	15	15	18	22	22	25	25
5	0	0	3	3	3	12	12	15	15	15	15	18	22	22	25	25

---

时间复杂度已经无法优化，但是空间复杂度可以优化成ｏ（Ｖ） 背包九讲中的解释如下： 那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。 个人理解 如果ｖ倒序计算（遍历）

f[v]=max{f[v],f[v-c[i]]+w[i]}; 　　　↑　　　↖同样可以理解成ｉ－１取得的结果 　　　可以理解成之前ｉ－１取得的结果　　　

由于ｖ是倒序，所有比ｖ大的表示ｉ层的结果，而≤的是ｉ－１层的结果，计算当前ｖ的只需要前ｉ－１层的结果即可 代码如下所示：

class Solution(): def zero_one(self,goods,max_V): f = [0] * (max_V+1) for i in range(len(goods)): for v in xrange(max_V,goods[i][0]-1,-1): f[v] = max(f[v],f[v-goods[i][0]]+goods[i][1]) return f goods = [[5,12],[4,3],[7,10],[2,3],[6,6]] test = Solution() print test.zero_one(goods,15)

过程中ｆ更新五轮，结果如下 [0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 15, 15, 15, 15, 15, 15] [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 15, 15, 22, 22, 22, 22] [0, 0, 3, 3, 3, 12, 12, 15, 15, 15, 15, 18, 22, 22, 25, 25] [0, 0, 3, 3, 3, 12, 12, 15, 15, 15, 15, 18, 22, 22, 25, 25]