? 關于0/1背包問題網上有非常多的博文,在此我謹記錄一下自己的理解。
? 問題表述:有N件物品和一個容量為V的背包。第i件物品的體積是C[i](0<=i<=N-1),價值是W[i]。求解將哪些物品裝入背包可使價值總和最大。每個物品最多只可以放入背包一次。
? 這個問題的經典解法思路如下:
? 我們用f[i][j]表示在考慮前i個物品時體積為j的背包的最大價值,注意,我們并不是把前i個物品全部放入背包,而是考慮i個物品中挑選一些放入背包,使得價值最大的那些情況。
? 首先,我們考慮只有1個物品(第0個)時,容量分別為0,1,...,V的各背包所包含物品的最大價值。很明顯,容量大于等于C[0]的背包的最大價值為W[0],容量小于C[0]的背包的最大價值為0。
? 然后,我們考慮再來一個(第i個)物品時,容量分別為0,1,...,V的各背包所包含物品的最大價值。對于某個背包,我們有兩種選擇:將該物品放入該背包或者不放入。
? 當我們將該物品放入某個體積為j的背包時,該背包的最大價值為f[i][j-C[i]]+W[i]。當我們不把該物品放入某個體積為j的背包時,該背包的最大價值為f[i-1][j]。所以在考慮前i個物品時,體積為j的背包的最大價值為f[i][j]=max{f[i-1][j],f[i][j-C[i]]+W[i]}.
? 迭代以上步驟,從i=0到N-1,最后得到的f[N-1][V]就是最后的答案。
? 上述算法的時間復雜度為O(VN),空間復雜度也是O(VN)。時間復雜度是最優的,而空間復雜度可以進一步優化:我們注意到在公式f[i][j]=max{f[i-1][j],f[i][j-C[i]]+W[i]}中,對于j從0到V,f[i][j]只與f[i-1][j]有關,而與i-2,i-3等情況下的f無關,所以我們只需要考慮前一次迭代(亦即i-1)的結果就可以。亦即f[j]=max{f[j],f[j-C[i]]+W[i]}.又因為在計算f[j]時用到了比j小的f:f[j-C[i]],所以在對j進行迭代時應該從后向前迭代:?
?
1 for ( int i=0;i<N;i++ ){ 2 for ( int j=V;j>=0;j-- ){ 3 if (j-item[i][0]>=0){ // 此處判斷是為了防止將j物品放入容量小于C[j]的背包中 4 f[j]=max(f[j],f[j-item[i][0]]+item[i][1 ]); 5 } 6 } 7 }
? 我們可以用一個例子來展示一下上述代碼迭代的過程。取V=10,N=3.三個物品的體積分別為3,4,5.價值分別為4,5,6,迭代過程中f數組的值為:
? 0 0 0 4 4 4 4 4 4 4 4
? 0 0 0 4 5 5 5 9 9 9 9
? 0 0 0 4 5 6 6 9 10 11 11
? 第一行為只考慮第1個物品的情況。所有容量大于等于3的背包的價值都為該物品的價值:4.
? 第二行為只考慮前2個物品的情況。所有容量大于等于7的背包可以同時容納前2個物品,價值為4+5=9,容量為4-6的背包可以容納第2個物品,價值為5,容量為3的背包可以容納第1個物品,價值為4.
? 第三行以此類推。
? 我們取最后1行的最后一個數字為結果,亦即考慮所有3個物品的體積為10的背包的最大價值,為11.
參考文獻:
? [1] 0/1問題 動態規劃法
? [2] 背包問題九講 第一講 0/1背包問題
? [3] 背包之0/1背包 完全背包 多重背包詳解
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
