f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。 現在我們來看第ｉ件物品： －－－如果選擇將第ｉ件物品放入，那么在放置前ｉ－１件物品的時候應該空出ｖ-ｃ[i]的容量，此時方程為ｆ[i-1][v-c[i]]+w[i] －－－如果選擇不將第ｉ件物品放入，那么此時的最大價值前第ｉ-1件放入容量為ｖ的背包獲得的最大價值決定，此時方程為f[i-1][v] 綜上所述，得出ｆ[i][v]
推薦大家走一遍實例，看一下下方結果輸出的表格，表格懂了，算法就懂了 假設當前有五件商品（重量，價值）（5，12），（4，3），（7，10），（2，3），（6，6） 背包容量為１５ 解決代碼如下所示 時間復雜度以及空間復雜度均為ｏ（Ｎ×Ｖ）
#coding=utf-8class 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 fgoods = [[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 fgoods = [[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]
新聞熱點
疑難解答
