背包問題的動(dòng)態(tài)規(guī)劃改進(jìn)算法

藍(lán)雯飛，吳子瑩，楊 波

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

背包問題的動(dòng)態(tài)規(guī)劃改進(jìn)算法

藍(lán)雯飛，吳子瑩，楊 波

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

在動(dòng)態(tài)規(guī)劃算法的基礎(chǔ)上提出了改進(jìn)算法，對于0-1背包問題，改進(jìn)了動(dòng)態(tài)規(guī)劃算法的狀態(tài)表示以減少需要計(jì)算的狀態(tài)個(gè)數(shù)來求解該問題；對于完全背包問題，簡化了動(dòng)態(tài)規(guī)劃算法狀態(tài)的決策依賴關(guān)系來求解該問題.實(shí)驗(yàn)結(jié)果表明：所提出的改進(jìn)算法在時(shí)空效率上具有一定的有效性和優(yōu)越性.

背包問題；動(dòng)態(tài)規(guī)劃；狀態(tài)表示；決策依賴

背包問題在現(xiàn)實(shí)生活中廣泛地應(yīng)用于需要基于有限資源進(jìn)行選擇判斷的領(lǐng)域[1]，如貨物裝載、投資組合、下料問題等[2]，因此對該問題的研究具有重要的實(shí)際意義.背包問題可以衍生出0-1背包問題、完全背包問題和多重背包問題等[3].解決0-1背包問題的動(dòng)態(tài)規(guī)劃算法的時(shí)空復(fù)雜度為O(nW)，本文通過簡化動(dòng)態(tài)規(guī)劃算法的狀態(tài)表示來改進(jìn)算法，改進(jìn)后算法的空間復(fù)雜度為O(W)，時(shí)間效率上有常數(shù)時(shí)間的優(yōu)化.解決完全背包問題的動(dòng)態(tài)規(guī)劃算法時(shí)間復(fù)雜度為O(nW(W/wi))，空間復(fù)雜度為O(nW)，本文通過簡化動(dòng)態(tài)規(guī)劃算法狀態(tài)的決策依賴關(guān)系改進(jìn)算法，改進(jìn)后算法的時(shí)空復(fù)雜度均為O(nW).

1 求解0-1背包問題的動(dòng)態(tài)規(guī)劃算法

1.1 常規(guī)動(dòng)態(tài)規(guī)劃算法RDP

建立規(guī)劃模型：子問題m(i,j)是前i個(gè)物品基于背包容量j所能得到的最大價(jià)值[7].根據(jù)0-1背包問題滿足最優(yōu)子結(jié)構(gòu)的性質(zhì)，建立狀態(tài)轉(zhuǎn)移方程如下：

m(i,j)=

問題迭代的初始條件為：

(2)

常規(guī)的動(dòng)態(tài)規(guī)劃算法RDP(Regular Dynamic Programming)的空間復(fù)雜度是O(nW)，時(shí)間復(fù)雜度為O(nW).利用動(dòng)態(tài)規(guī)劃方法，問題可以在O(nW)的時(shí)間效率內(nèi)解決[8].但算法的時(shí)間復(fù)雜度與背包容量有關(guān)[9].當(dāng)背包容量較小時(shí)，算法的時(shí)間復(fù)雜度是可以接受的.但是當(dāng)W≥2n時(shí)，該動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O(n2n).

1.2 動(dòng)態(tài)規(guī)劃算法改進(jìn)思路

在0-1背包問題中，公式(1)同時(shí)用容量較小的背包和較少的物品種類來縮小原問題的規(guī)模，即子問題m(i,j)表示前i件物品基于背包容量j所能得到的最大價(jià)值.子問題m(i,j)的計(jì)算只依賴于m(i-1,·)，即當(dāng)前子問題的計(jì)算只依賴于算法中前一輪子問題的解.因此可以考慮改進(jìn)狀態(tài)表示，用一維的子問題狀態(tài)m(j)表示容量為j的背包可以裝入物品的最大價(jià)值.

依據(jù)公式(1)，子問題m(i,j)是由m(i-1,j)和m(i-1,j-wi)兩個(gè)子問題遞推而來.對于一維的子問題m(j)，若算法采用順推的方式，在計(jì)算子問題“前i個(gè)物品基于背包容量j能得到的最大總價(jià)值”m(j)時(shí)，m(j-wi)保存的是子問題“前i個(gè)物品基于背包容量j-wi所能得到的最大總價(jià)值”，這與上述狀態(tài)轉(zhuǎn)移方程中的決策不符.若算法采用逆推的方式，在每次計(jì)算中以背包容量遞減的方式考慮子問題m(j)，這樣可以保證在計(jì)算子問題m(j)時(shí)，m(j)和m(j-wi)保存的是所依賴的子問題的解.改進(jìn)后的狀態(tài)轉(zhuǎn)移方程如下：

(3)

迭代的初始條件為：

(4)

改變動(dòng)態(tài)規(guī)劃算法的規(guī)劃順序后，時(shí)間復(fù)雜度為O(nW)，算法的空間復(fù)雜度由O(nW)優(yōu)化到O(W).動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度主要由每次狀態(tài)轉(zhuǎn)移所涉及的狀態(tài)數(shù)、每次狀態(tài)轉(zhuǎn)移的時(shí)間、問題中需要計(jì)算的狀態(tài)總數(shù)這三部分組成，在不改變前兩個(gè)部分的基礎(chǔ)上，限制問題中狀態(tài)計(jì)算的上下界，減少算法中需要計(jì)算的狀態(tài)個(gè)數(shù)，以此來提高算法的時(shí)間效率.

1.3 高效的動(dòng)態(tài)規(guī)劃算法EDP

公式(3)用逆推的方式解決問題.仔細(xì)分析算法發(fā)現(xiàn)其中仍然存在冗余，當(dāng)依次考慮到第n件物品時(shí)，事實(shí)上前n-1件物品的最優(yōu)裝載方式已經(jīng)確定，此時(shí)只需一次計(jì)算，計(jì)算公式如下：

(5)

狀態(tài)轉(zhuǎn)移方程可以被優(yōu)化為：

(6)

2 求解完全背包問題的動(dòng)態(tài)規(guī)劃算法

2.1 傳統(tǒng)動(dòng)態(tài)規(guī)劃算法NDP

0-1背包問題中每種物品只有兩種決策：選或不選；完全背包問題中物品有選擇0件、選擇1件、選擇2件、…、選擇?W/wi」件等多種策略，雖然每種物品有無限件，但對于一件具體的物品，依然只有放進(jìn)背包或不放進(jìn)背包兩種策略[11].

借用解決0-1背包問題的思想[12]，定義子問題m(i,j)為前i件物品基于背包容量j所能得到的最大價(jià)值.據(jù)此狀態(tài)轉(zhuǎn)移方程為：

m(i,j)=max{m(i-1,j-x·wi)+x·vi,0≤x·wi≤j}.

(7)

迭代的初始條件為：

m(1,j)=x·v1,0≤x·w1≤j.

(8)

2.2 動(dòng)態(tài)規(guī)劃算法改進(jìn)

完全背包問題的優(yōu)化措施：對于兩件物品i,j，若滿足約束條件wi≥wj,vi≤vj，則在將物品放入背包時(shí)，可以不考慮第i種物品.因?yàn)樵谌魏吻闆r下將裝入背包的第i種物品替換為重量小、價(jià)值高的第j種物品時(shí)，背包的總價(jià)值不會(huì)變小.此優(yōu)化措施可以減少物品的種類，提高算法執(zhí)行的效率.但對于任意的兩種物品i,j，不存在wi≥wj,vi≤vj關(guān)系時(shí)不能去掉任何物品.

分析公式(7)可以發(fā)現(xiàn)當(dāng)計(jì)算子問題m(i,j)時(shí)，方程引用了x=0,1,2,…，?j/wi」每一種決策.令x=?j/wi」，計(jì)算子問題m(i,j)時(shí)，已求解的子問題m(i,j-wj)正是前i-1種物品和x-1件第i種物品基于背包容量j-wi所能獲得的最大價(jià)值.因此狀態(tài)轉(zhuǎn)移方程可以被優(yōu)化為：

m(i,j)=

我們把本文提出的動(dòng)態(tài)規(guī)劃改進(jìn)算法稱為優(yōu)化動(dòng)態(tài)規(guī)劃算法ODP(Optimization of Dynamic Programming).ODP減少了每次狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)，將方程中每次狀態(tài)轉(zhuǎn)移涉及的狀態(tài)數(shù)從O(W/wi)降為O(1)，將算法的時(shí)間復(fù)雜度優(yōu)化到O(nW).

3 性能測試結(jié)果與分析

實(shí)驗(yàn)將驗(yàn)證改進(jìn)后的算法在解決0-1背包問題和完全背包問題時(shí)物品重量對時(shí)間效率的影響，按物品重量與背包容量的關(guān)系將實(shí)驗(yàn)數(shù)據(jù)分為5類，即物品重量wi分別在[1,W/20],[W/20,W/10],[W/10,3W/20],[3W/20,W/5],[1,W/5]范圍內(nèi)隨機(jī)分布，令背包容量W=1000.

3.1 0-1背包問題的測試結(jié)果與分析

表1是不同問題規(guī)模不同物品重量分布時(shí)算法的運(yùn)行時(shí)間，圖1是不同問題規(guī)模物品重量在[1,200)分布時(shí)RDP和EDP的運(yùn)行時(shí)間比較.下面從兩個(gè)方面分析這兩種算法的時(shí)間效率差異.

表1 不同問題規(guī)模不同物品重量分布時(shí)算法的運(yùn)行時(shí)間

圖1 RDP和EDP運(yùn)行時(shí)間比較Fig.1 Comparison of running time between RDP and EDP

(1)不同數(shù)據(jù)類別的0-1背包問題. 當(dāng)物品重量與背包容量有不同關(guān)系時(shí)，RDP有不同的狀態(tài)轉(zhuǎn)移關(guān)系，影響算法時(shí)間效率.EDP在RDP基礎(chǔ)上，改變算法的規(guī)劃方向，分析狀態(tài)之間的依賴關(guān)系，緊致問題中所需要計(jì)算狀態(tài)的界限條件.這個(gè)界限條件與物品重量有關(guān)系：當(dāng)物品重量增加時(shí)，問題中需要計(jì)算的狀態(tài)個(gè)數(shù)減少.由于每次狀態(tài)轉(zhuǎn)移過程中所涉及的狀態(tài)數(shù)和轉(zhuǎn)移時(shí)間不變，這樣就從整體上提高了算法的時(shí)間效率.

如圖1所示，在相同物品數(shù)量規(guī)模的情況下，EDP的運(yùn)行時(shí)間比RDP的運(yùn)行時(shí)間少，而且隨著物品數(shù)量規(guī)模的增大，兩條曲線之間的距離越來越大，EDP運(yùn)行時(shí)間會(huì)明顯比RDP的運(yùn)行時(shí)間少.

(2) 相同數(shù)據(jù)類別相同數(shù)據(jù)規(guī)模的0-1背包問題. 如表1所示，物品重量在[1,50), [150,200), [1,200)隨機(jī)分布時(shí)，在相同物品數(shù)量規(guī)模的情況下，EDP的運(yùn)行時(shí)間均比RDP的運(yùn)行時(shí)間少.

無論所考慮物品重量較小(即物品重量在[1,50)隨機(jī)分布)，還是物品重量較大(在[150,200)分布)，或是所考慮物品中既有小重量物品又有大重量物品(在[1,200)隨機(jī)分布)，EDP的時(shí)間效率都要比RDP的時(shí)間效率高.

EDP的時(shí)間效率比RDP的時(shí)間效率高，原因在于EDP對問題中需要計(jì)算的狀態(tài)做了上下界約束，減少了需要計(jì)算的狀態(tài)個(gè)數(shù)，因此減少問題中需要計(jì)算的狀態(tài)總個(gè)數(shù)可以有效地提高動(dòng)態(tài)規(guī)劃算法的時(shí)間效率.

3.2 完全背包問題的測試結(jié)果與分析

表2是不同問題規(guī)模物品重量在[1,50),[50,100),[100,150)上隨機(jī)分布時(shí)算法的運(yùn)行時(shí)間，表3是不同問題規(guī)模物品重量在[150,200),[1,200)上隨機(jī)分布時(shí)算法的運(yùn)行時(shí)間，圖2是不同問題規(guī)模物品重量在[1,200)分布時(shí)NDP、BDP和ODP的運(yùn)行時(shí)間比較.下面從2個(gè)方面分析這3種算法的時(shí)間效率差異.

表2 物品重量在[1,50), [50,100), [100,150)上隨機(jī)分布算法的運(yùn)行時(shí)間

表3 物品重量在[150,200), [1,200)上隨機(jī)分布算法的運(yùn)行時(shí)間

Tab.3 Running time of the algorithm on the random distribution of the item weight in [150,200), [1,200) ms

(1)不同數(shù)據(jù)類別的完全背包問題. 如圖2所示，在相同物品數(shù)量規(guī)模的情況下，ODP的運(yùn)行時(shí)間比NDP、BDP的運(yùn)行時(shí)間少，而且隨著物品數(shù)量規(guī)模的增大，3條曲線之間的差異愈加顯著，ODP的運(yùn)行時(shí)間明顯比NDP、BDP的運(yùn)行時(shí)間少.

圖2 NDP、BDP和ODP運(yùn)行時(shí)間比較Fig.2 Comparison of running time among NDP, BDP and ODP

NDP和BDP在求解不同數(shù)據(jù)類別的完全背包問題時(shí)，隨著物品重量的增加，算法的時(shí)間效率會(huì)相應(yīng)地提高.ODP在NDP的基礎(chǔ)上減少了每次狀態(tài)轉(zhuǎn)移所依賴的狀態(tài)數(shù).由于ODP的時(shí)間效率與物品重量并沒有直接關(guān)系，因此ODP在求解不同數(shù)據(jù)類別的完全背包問題時(shí)表現(xiàn)出基本一致的性能.

(2) 相同數(shù)據(jù)類別相同數(shù)據(jù)規(guī)模的完全背包問題. 如表2、表3所示，物品重量在[1,50)隨機(jī)分布時(shí)，在相同物品數(shù)量規(guī)模的情況下，ODP的運(yùn)行時(shí)間明顯比NDP、BDP的運(yùn)行時(shí)間少，約是NDP運(yùn)行時(shí)間的1/20,約是BDP運(yùn)行時(shí)間的1/3；物品重量在[150,200)隨機(jī)分布時(shí)，在相同物品數(shù)量規(guī)模的情況下，EDP的運(yùn)行時(shí)間也均比NDP、BDP的運(yùn)行時(shí)間少；物品重量在[1,200)隨機(jī)分布時(shí)亦是如此.

BDP比NDP的時(shí)間效率要高.BDP將完全背包問題轉(zhuǎn)化為0-1背包問題的過程中運(yùn)用了二進(jìn)制思想，減少了轉(zhuǎn)化后的物品件數(shù)，而NDP是將問題直接進(jìn)行轉(zhuǎn)化.本文通過對NDP的研究，分析出狀態(tài)間有效的決策依賴關(guān)系，發(fā)現(xiàn)NDP在每次狀態(tài)轉(zhuǎn)移的過程中涉及了大量無效的狀態(tài)，而ODP明顯減少了每次狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)，因此提高了算法的時(shí)間效率.

4 結(jié)束語

動(dòng)態(tài)規(guī)劃是求解背包問題的一種經(jīng)典算法.求解0-1背包問題時(shí)，論文通過對RDP中需要計(jì)算的狀態(tài)做出了上下界約束，進(jìn)而得到改進(jìn)后的EDP.求解完全背包問題時(shí)，通過對NDP分析，發(fā)現(xiàn)每次狀態(tài)轉(zhuǎn)移的過程中涉及了大量無效的狀態(tài)，分析出狀態(tài)間有效的決策依賴關(guān)系，從而得到優(yōu)化后的ODP算法.最后通過實(shí)驗(yàn)驗(yàn)證了論文提出的EDP和ODP的有效性和優(yōu)勢.今后將繼續(xù)研究背包型動(dòng)態(tài)規(guī)劃，使得該問題的應(yīng)用價(jià)值能更好地發(fā)揮出來.

[1] Bologna T P. Dynamic programming algorithms for the zero-one knapsack problem[J]. Computing, 1980, 25 (1): 29-45.

[2] Sitarz S. Dynamic programming with ordered structures: theory, examples and applications[J]. Fuzzy Sets and Systems,2010,161(20):2623-2641.

[3] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms[M]. Massachusetts: The MIT Press, 2012:101-120.

[4] Bellman R. Dynamic programming[M]. Princeton: Princeton University Press,1957:60-80.

[5] 李 端，錢富才，李 力，等. 動(dòng)態(tài)規(guī)劃問題研究[J]. 系統(tǒng)工程理論與實(shí)踐，2007,27(8):56-64.

[6] 李北斗. 關(guān)于0-1背包問題的算法研究[J]. 計(jì)算機(jī)與數(shù)字工程，2008,36(5):23-26.

[7] 孫懷影，耿寅融，單 謙. 求解0-1背包問題的一種新混合算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2012,48(4):50-53.

[8] 朱閱岸. 解0-1背包問題的算法比較和改進(jìn)[D]. 廣州：暨南大學(xué)，2011.

[9] Cosnard M, Ferreira A G, Herbelin H. The two list algorithm for a knapsack problem[J]. Parallel Computing, 1989,34(9):385-388.

[10] Martello S, Pisinger D, Toth P. New trends in exact algorithms for the 0-1 knapsack problem[J]. European Journal of Operational Research, 2010, 123(2):325-332.

[11] Pisinger D. Where are the hard knapsack problems[J]. Computes and Operations Research, 2005,32(9):2271-2284.

[12] 馬 良，王龍德. 背包問題的螞蟻優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用，2001,21(8):4-5.

[13] 劉汝佳，黃 亮. 算法藝術(shù)與信息學(xué)競賽[M]. 北京：清華大學(xué)出版社，2004: 35-48.

Improved Dynamic Programming Algorithms for the Knapsack Problem

Lan Wenfei, Wu Ziying, Yang Bo

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

In this paper, we proposed improved algorithms based on dynamic programming thinking. For the 0-1 knapsack problem, we improved the status representation of dynamic programming algorithm to reduce the number of states needed to calculate. For the complete knapsack problem, we simplified the decision dependency status of dynamic programming algorithm to solve the problem. Experimental results showed that the improved algorithms have some validity and superiority in space and time efficiency.

knapsack problem；dynamic programming；state representation；decision dependency

2016-06-14

藍(lán)雯飛(1966-)，女，教授，研究方向：數(shù)據(jù)庫技術(shù)和軟件新技術(shù)，E-mail:lanwenfei1@163.com; 吳子瑩(1990-)，女，碩士研究生，研究方向：數(shù)據(jù)挖掘，E-mail:1047237684@qq.com

國家自然科學(xué)基金資助項(xiàng)目(71003038)

TP301

A

1672-4321(2016)04-0101-05