一種求解分組0-1背包問題的動態規劃法

摘 要 研究了分組0-1背包問題，提出了一種動態規劃解決方法，在物品總數為n個和背包承重量為W時，遞推過程的復雜度為O(nW)，回溯過程的復雜度為O(n).計算實例表明利用該方法易于找到最優解.

關鍵詞 背包問題;NP完全;動態規劃

中圖分類號 TP301 文獻標識碼 A

A Dynamic Programming Method for

Classified 0-1 Knapsack Problem

JIANG Ya-jun1， YI Xue-jun2

(1.Department of Computer and Communication Engineering， Hunan University of Science and Engineering， Yongzhou，

Hunan 425100 China; 2.College of Mathematics and Econometrics， Hunan University， Changsha，Hunan 410082 China)

Abstract This paper studied the classified 0-1 knapsack problem， and proposed a dynamic programming method. The complexity of the recursive process is O(nW)， and the complexity of the traceback process is O(n)， where n is the total number of goods and W is the bearing weight of the knapsack. The example shows that it is easy to find the optimal solution by the method.

Key words Knapsack Problem; NP-complete; Dynamic Programming

1 引 言

0-1背包問題屬于NP完全問題，可以表述為：已知n個物品和一個承重量為W的背包，每個物品i的重量為wi，價值為vi（i=1，2，…，n），現要從這n個物品中選出若干件放入背包，使得裝入背包物品的總重量不超過W，且總價值達到最大.0-1背包問題在信息安全、工程決策等領域中有著極為重要的應用［1-5］，對0-1背包問題擴展研究，如0-1二次背包問題［6］、多目標0-1背包問題［7］、多維0-1背包問題［8］等，有著十分重要的應用價值和學術意義.

本文將傳統的0-1背包問題擴展為分組0-1背包問題，闡述了分組0-1背包問題的動態規劃解決方案，為背包問題的應用拓展了新的思路.

2 分組0-1背包問題的數學模型

在分組0-1背包問題中，所有物品被分成若干組，在裝入固定承重量的背包時，要求每組物品不能全部取完并且總價值最大.在選擇裝入背包的物品時，對每個物品只有兩種選擇，即裝入背包或不裝入背包.不能將物品裝入背包多次，也不能只裝入部分的物品.在這里假設所有物品的重量和背包的承重量都是正整數.分組0-1背包問題的數學模型描述為：

給定n個物品，分成r組，設為

{G11，…，G1s1，…，Gj1，…，Gjsj，…，Gr1，…，Grsr}，

其中∑rj=1sj=n，r＞1，sj＞1（j=1，2，…，r）.各物品的重量和價值分別為：

{w11，…，w1s1，…，wj1，…，wjsj，…，wr1，…，wrsr}，

{v11，…，v1s1，…，vj1，…，vjsj，…，vr1，…，vrsr}，

其中wji＞0，vji＞0，i=1，…，sj，j=1，…，r.給定W＞0，求解n元0-1向量=(x11，…，x1s1，…，xj1，…，xjsj，…，xr1，…，xrsr)，使得當∑rj=1∑sji=1xjiwji≤W，∑sji=1xji＜sj時，∑rj=1∑sji=1xjivji達到最大.

3 動態規劃法

為了用動態規劃法求解分組0-1背包問題，可以用一個動態規劃表M跟蹤遞推，行對應于每一個物品，列對應于背包的承重量， M(j)［i，k］代表第∑j－1l=1sl+i行第k列單元格的值，它表示當背包承重量為k時，從物品G11，…，G1s1，…，Gj1，…，Gji中選取但各組不全部取完裝入到背包中的最大價值.表格的填充從上到下，從左到右.

定理1 當0≤k≤W， 0≤i≤sj，1≤j≤r時，設M(1)［0，k］=0，M(j)［i，0］=0；當2≤j≤r時，設M(j)［0，k］=M(j－1)［sj－1，k］，則分組0-1背包問題中最優子集的最大價值遞推公式為：

1）若1≤i＜sj，則

經 濟 數 學第 29卷第1期蔣亞軍等：一種求解分組0-1背包問題的動態規劃法

M(j)［i，k］=M(j)［i－1，k］，k＜wji，max {M(j)［i－1，k］，M(j)［i－1，k－wji］+vji}，k≥wji.(1）

2）若i=sj，則

M(j)［sj，k］=

M(j)［sj－1，k］，k＜wjsj，max {M(j)［l－1，k－∑sjτ=l+1wjτ］+∑sjτ=l+1vjτ，l=1，2，…，sj}，k≥∑sji=1wji，max {M(j)［sj－1，k］，M(j)［sj－1，k－wjsj］+vjsj}，wjsj≤k＜∑sji=1wji.（2）

證明 對于有序物品組{G11，…，G1s1，…，Gj1，…，Gjsj，…，Gr1，…，Grsr}中第l個物品，存在唯一(i，j)，使得l=s1+…+sj－1+i，這里1≤i≤sj，1≤j≤r.顯然當1≤l≤s1時，即j=1時，直接令l=i.這里特別說明，當某組只有一個物品時，顯然該組可以不作考慮，故這里假設sj＞1，j=1，2，…，r.

下面用歸納法來證明由遞推公式給出的M(j)［i，k］滿足相應的最大價值：

1）當l=1時(對應(i，j)=(1，1))，易知對于任意k，由公式（1）給出的M(1)［1，k］滿足最大價值.

當l=2時(對應(i，j)=(2，1))，易知對于任意k，由公式（1）或公式(2) 給出的M(1)［2，k］滿足最大價值.

2）假設1≤l≤m時（對應唯一(i，j)），對于任意k，由公式（1）或公式(2) 給出的M(j)［i，k］滿足最大價值.

3）下面證明對于l=m+1時（對應唯一i′，j′），對于任意k，由公式（1）或公式（2）給出的M(j′)［i′，k］也滿足最大價值.

分三種情形進行討論：

（ⅰ）m=s1+…+sj′－1+i′－1（這里1≤i′＜sj′），

（ⅱ）m=s1+…+sj′－2+sj′－1，

（ⅲ）m=s1+…+sj′－1+sj′－1.

1）對于情形（ⅰ）， 當l=m+1時（對應唯一i′，j′=i+1，j），因為i′＜sj′，第m+1個物品不是所在組最后一個，則該物品被取與否，該組都不會出現選滿的情形.

當k＜wj′i′時，則第m+1個物品不能被取，由歸納假設M(j′)［i′－1，k］=M(j)［i，k］滿足最大價值，因而M(j′)［i′，k］=M(j′)［i′－1，k］.

當k≥wj′i′時，則第m+1個物品有可能被取或不取兩種情形：當第m+1個物品不取時，由歸納假設M(j′)［i′－1，k］=M(j)［i，k］滿足最大價值，所以M(j′)［i′，k］=M(j′)［i′－1，k］；而當第m+1個物品被取時，由歸納假設M(j′)［i′－1，k－wj′i′］=M(j)［i，k－wj′i′］滿足最大價值，所以M(j′)［i′，k］=M(j′)［i′－1，k－wj′i′］+vj′i′.綜合前述兩種情形有：M(j′)［i′，k］=max {M(j′)［i′－1，k］，M(j)［i′－1，k－wj′i′］+vj′i′}.

由上可知，當l=m+1（對應唯一i′，j′），且m=s1+…+sj′－1+i′－1時（這里1≤i′＜sj′）， 有

M(j′)［i′，k］=

M(j′)［i′－1，k］，k＜wj′i′max {M(j′)［i′－1，k］，k≥wj′i′M(j)［i′－1，k－wj′i′］+vj′i′}

2）對于情形（ⅱ），當l=m+1（對應唯一(i′，j′)=(1，j+1)），因為sj′＞1，第m+1個物品是所在組第1個，則該物品被取與否，該組都不會被全部選滿.

當k＜wj′1時，則第j′類中第1個物品不能被選擇，由歸納假設M(j′)［1，k］=M(j′－1)［sj′－1，k］=M(j′)［0，k］.

當k≥w(j′)1時，則第j′類中第1個物品有可能被取或不取兩種情形：當第1個物品不取時，由題設及歸納假設M(j′)［0，k］=M(j′－1)［sj′－1，k］滿足最大價值，所以M(j′)［1，k］=M(j′－1)［sj′－1，k］；而當第1個物品被取時， 由題設及歸納假設M(j′)［0，k－wj′1］=M(j′－1)［sj′－1，k－wj′1］滿足最大價值，所以M(j′)［1，k］=M(j′)［0，k－wj′1］+vj′1.綜合前述兩種情形有：M(j′)［1，k］=max {M(j′)［0，k］，M(j′)［0，k－w(j′)1］+v(j′)1}.

由上可知，當l=m+1（對應唯一(i′，j′)，且m=s1+…+sj′－2+sj′－1時，有

M(j′)［1，k］=M(j′)［0，k］，k＜wj′1;max {M(j′)［0，k］，

M(j′)［0，k－wj′1］+vj′1}，k≥wj′1.

3）對于情形（ⅲ），當l=m+1時（對應(i′，j′)=(sj′，j′)=(i+1，j)），這里i=sj－1，第m+1個物品是所在組最后1個.

當k＜wj′sj′時，則第m+1個物品不能被選擇，由歸納假設M(j′)［i′－1，k］=M(j)［i，k］滿足最大價值，所以M(j′)［i′，k］=M(j′)［i′－1，k］.

當k≥∑sj′i=1wj′i時， 有sj′種情形：即當l=1，2，…，sj′時，第j′組中第l個物品不取，而之后的物品都取.由歸納假設M(j′)［l－1，k－∑sj′l=l+1wj′l］滿足最大價值，所以

M(j′)［sj′，k］=max {M(j′)［l－1，k－∑sj′τ=l+1wj′τ］

+∑sj′τ=l+1vj′τ，l=1，2，…，sj′}.

當wj′sj′≤k＜∑sj′i=1wj′i時， 此時第m+1個物品有可能被取或不取兩種情形:當第m+1個物品不取時，由歸納假設M(j′)［i′－1，k］=M(j)［i，k］滿足最大價值，所以M(j′)［i′，k］=M(j′)［sj′，k］=M(j′)［i′－1，k］=M(j′)［sj′－1，k］；而當第m+1個物品被取時，由歸納假設M(j′)［sj′-1，k-wj′sj′］滿足最大價值，所以M(j′)［sj′，k］=M(j′)［sj′-1，k-wj′sj′］+v(j′)sj′.綜合前述兩種情形有

M(j′)［sj，k］=max{M(j′)［sj′-1，k］，

M(j′)［sj，j′-1，k-wj′sj′］+vj′sj′}.

由式（1）、式（2）和式（3）可知，當l=m+1（對應唯一i′，j′），且m=s1+…+sj′－1+sj′－1 時，有

M(j′)［sj′，k］=

M(j′)［sj′－1，k］，k＜wjsj′，max {M(j′)［l－1，k－∑sj′τ=l+1wj′τ］+∑sj′τ=l+1vj′τ，l=1，2，…，sj}，k≥∑sj′i=1wj′i，max {M(j′)［sj′－1，k］，M(j′)［s(j′)－1，k－wj′sj′］+vj′sj′}，wj′sj′≤k＜∑sji=1wj′i.

由1）、2）和3）可知，對于（ⅰ）、（ⅱ）和（ⅲ）三種情形證明了對于l=m+1（對應唯一(i′，j′)），由遞推公式（1）或（2）給出的M(j′)［i′，k］滿足最大價值要求.

因而對于任意1≤l≤n（對應的(i，)）和任意k，由遞推公式（1）或（2）給出的M(j)［i，k］為對應的最大價值.證畢.

為了通過動態規劃表M求取最優子集，定義一個回溯表F來跟蹤上述遞推過程，行對應于每一個物品，列對應于背包的承重量.令

F(j)［i，k］=

0，M(j)［i，k］=M(j)［i－1，k－wji］+vji;sj－t，M(j)［sj，k］=M(j)［t，k－∑sjτ=t+2wjτ)］+∑sjτ=t+2vjτ， t=0，1，…，sj－2;1M(j)［i，k］=M(j)［i－1，k］.（3）

回溯過程從動態規劃表M的最后一項M(r)［sr，T′］直到M(1)［0，0］，回溯方法描述為：

1）若F(j)［i，k］=0，則回溯至M(j)［i－1，k－wji］，此時令xji=1；

2）若F(j)［i，k］=1，則回溯至M(j)［i－1，k］，此時令xji=0；

3）若F(j)［i，k］=sj－t＞1，則回溯至M(j)［i－(sj－t)，k－∑sjτ=t+2wjτ)］，此時令xjt+2=xjt+3=…=xjsj=1，xjt+1=0.

4 計算實例

給定三組物品{G11，G12，G13，G21，G22，G23，G31，G32}，它們的重量和價值如表1所述，設背包的承重量W=6.則根據公式（1）和（2）可計算出動態規劃表M，如表2如述.根據公式（3）可計算出回溯表F，如表3如述.由表2和表3，回溯可以得到=(x11，x12，x13，x21，x22，x23，x31，x32)=(1，0，1，0，1，1，0，1).故最優子集為{G11，G13，G22，G23，G32}，最大價值為33元.

5 結 論

本文研究了分組0-1背包問題，并提出了解決分組0-1背包問題的動態規劃解決方法，在物品總數為n個和背包承重量為W時，生成動態規劃表M的復雜度為O(nW)，生成回溯表F的復雜度為O(n).該方法思路簡單，容易理解，計算實例驗證了利用該方法易于找到最優解.

參考文獻

［1］ B Chor， R Rivest. A knapsack-type public key cryptosystem based on arithmetic in finite fields［J］.IEEE Transactions on Information Theory，1988，34(5):901-909.

［2］ C Laih， J Lee， L Harn， et al. Linearly shift knapsack public-key cryptosystem［J］.IEEE Journal of Selected Areas Communication，1989，7(4):534-539.

［3］ D Yao， K Frikken， M Atallah， et al. Private information:to reveal or not to reveal［J］. ACM Transactions on Information and Systems Security， 2008， 12(1):1-27.

［4］ 張生， 魏忠華， 何尚錄等. 0-1背包問題在限額投資決策中的應用及其擾動分析［J］.內蒙古師范大學學報:自然科學漢文版，2007，36(5):595-598.

［5］ 張琳， 胡正華， 黃河. 基于背包問題的散貨航次方案優選方法研究［J］.價值工程，2011，20(5):221-222.

［6］ 謝濤， 陳火旺， 康立山. 二次背包問題的一種快速解法［J］. 計算機學報，2004，27(9):1162-1169.

［7］ 熊小華， 寧愛兵， 馬良. 多目標0-1背包問題的元胞競爭決策算法［J］.計算機應用研究，2010，27(10):3680-3683.

［8］ 王凌， 王對堯， 方晨. 一種求解多維背包問題的混合分布估計算法［J］.控制與決策，2011，26(8):1121-1125.