貪心核加速動態規劃算法求解折扣{0-1}背包問題

史文旭 楊洋 鮑勝利

摘 要：針對現有動態規劃算法求解折扣{0-1}背包問題（D{0-1}KP）緩慢的問題，基于動態規劃思想并結合新型貪心修復優化算法（NGROA）與核算法，通過縮小問題規模加速問題求解來提出一種貪心核加速動態規劃（GCADP）算法。首先利用NGROA對問題進行貪心求解，得到非完整項;然后通過計算得到模糊核區間的半徑和模糊核區間范圍;最后對于模糊核區間內的物品及同一項集內的物品利用基礎動態規劃（BDP）算法求解。實驗結果表明：GCADP算法適用于求解D{0-1}KP，且在求解速度上相比BDP算法平均提升了76.24%，相比FirEGA算法平均提升了75.07%。

Abstract： As the existing dynamic programming algorithm cannot quickly solve Discounted {0-1} Knapsack Problem （D{0-1}KP）， based on the idea of dynamic programming and combined with New Greedy Repair Optimization Algorithm （NGROA） and core algorithm， a Greedy Core Acceleration Dynamic Programming （GCADP） algorithm was proposed with the acceleration of the problem solving by reducing the problem scale. Firstly， the incomplete item was obtained based on the greedy solution of the problem by NGROA. Then， the radius and range of fuzzy core interval were found by calculation. Finally， Basic Dynamic Programming （BDP） algorithm was used to solve the items in the fuzzy core interval and the items in the same item set. The experimental results show that GCADP algorithm is suitable for solving D{0-1}KP. Meanwhile， the average solution speed of GCADP improves by 76.24% and 75.07% respectively compared with that of BDP algorithm and FirEGA （First Elitist reservation strategy Genetic Algorithm）.

Key words： Discounted {0-1} Knapsack Problem （D{0-1}KP）; Greedy Core Acceleration Dynamic Programming （GCADP） algorithm; New Greedy Repaired Optimization Algorithm（NGROA）; core algorithm; Basic Dynamic Programming （BDP）

0 引言

折扣{0-1}背包問題（Discounted{0-1} Knapsack Problem， D{0-1}KP）是經典的{0-1}背包問題（{0-1} Knapsack Problem，{0-1}KP）的一個拓展形式[1-6]，通過數學模型刻畫實際商業活動中折扣銷售、捆綁銷售等現象，對這類問題進行最優化求解，達到獲利最大化。D{0-1}KP可簡單理解為A物品售價40元，B物品售價50元，同時購買A，B記為購買物品C只需支出80元或其他小于90元的價格。在現實商業銷售案例中，如“黑色星期五”“雙十一”等大型購物節，通過D{0-1}KP能夠很好地使客戶在項目決策得到最優方案，銷售商也能夠通過D{0-1}KP更有針對性地設計自己的銷售方案。利用D{0-1}KP使得商業價值達到最大化，在實際商業問題中，具有廣闊的應用前景。

對于D{0-1}KP的數學模型，主要有三類數學模型：Guder[1]和Guldan[2]分別提出單目標與多目標第一數學模型;賀毅朝等[3]通過將二進制編碼方式改為實數類編碼方式提出第二數學模型;楊洋等[4]通過改變二進制編碼個體對應原則，提出簡化數學模型。三類模型均存在虛擬物品C，即同時購買物品A和物品B，但不同算法表達方式不同。考慮到動態規劃算法特殊性，因而本文使用D{0-1}KP第一數學模型。

對于D{0-1}KP的求解算法方面，主要有精確算法求解及群智能算法求解兩大方面。對于精確算法，主要是基于動態規劃算法，如Rong等[5]結合背包問題中的核問題對D{0-1}KP提出了基于核問題的基礎動態規劃（Basic Dynamic Programming， BDP）等。He等[6]通過對偶思想，將動態規劃中最大價值轉換為求解最小質量，提出針對D{0-1}KP的新精確算法（New Exact algorithm for D{0-1}KP， NE-DKP）。對于群智能算法[3-4，7-15]則成果相對較多，如：遺傳算法[3-4，7-8]、帝蝴蝶算法[9-10]、烏鴉算法[12-13]等成果。

基于文獻[7]中提出的新型貪心修復優化算法（New Greedy Repaired Optimization Algorithm， NGROA），通過核算法[8]縮小問題規模，加速問題求解，再利用動態規劃算法對問題進行求解，提出貪心核加速動態規劃（Greedy Core Acceleration Dynamic Programming， GCADP）算法。利用GCADP求解四類大規模D{0-1}KP實例，分析其結果。

2 改進核算法

利用價值密度對背包問題進行貪心求解是一種常見的有效手段，因其結構簡單，運算迅速，近似結果良好受到廣泛應用。又因為價值密度貪心算法求得的近似個體與精確解個體的主要差異在于鄰近第一個超出背包承重的物體序號附近，根據這一特性，Balas等[16]于1980年提出核算法。

2.1 精確核算法

對于{0-1}KP而言，核算法可理解為對于物品規模為n的解空間X1×n分為三個子空間的直和，即X1×n=X11×n1⊕X21×n2⊕X31×n3。其中，子空間X1中的分量均取值為1，即{X11×n1=1|1≤i≤n1};子空間X3中的分量均取值為0，即{X31×n3=0|1≤i≤n3}，而子空間X2即為精確核算法的解，也即核區間，接下來只需對X2進一步求解即可，則將問題規模從dim（X1×n）=n縮減為dim（X21×n2）=n2，從而達到加速的效果。

則問題化為首先需要思考如何對問題進行精確劃分子空間，但對問題進行精確的時間復雜度此句不通順，需調整與精確求解{0-1}KP相同但對問題進行精確劃分子空間的時間復雜度與精確求解{0-1}KP的時間復雜度相同[17]，則問題仍然是一個非確定性多項式難題（Non-deterministic Polynomial hard， NP-hard）問題，較難直接求解，因此有必要考慮一種快速、簡單的方法尋找近似核區間替代精確核區間。

2.2 近似核算法

類似文獻[5，18]中的方法，近似核算法定義模糊核區間（Fuzzy Core Interval， FCI）[s，t][18]如下：

X∈{0，1}1×n表示為該背包問題的貪心近似解。其中，xi=0Xi是個數值，應該不是向量、矢量或矩陣吧？表示不選取第i個物品;xi=1表示選取第i個物品。s為核區間下界，t為上界;b為非完整項（break item）;r為核半徑;且n為經驗數值[16]，n為問題規模;N為自然數集。

2.3 貪心策略

D{0-1}KP與{0-1}KP在利用貪心思想求解近似解時，最大的不同便在于D{0-1}KP在選擇當前價值密度最大項時，會出現同一項集內的多個物品同時被選擇的情況。傳統貪心修復優化算法（Greedy Repaired Optimization Algorithm， GROA）在處理這類問題時，選擇價值密度最大項。目標函數并非是選擇價值密度最大項，而是價值最大項。這就導致文獻[5]中，結合核算法的稀疏點動態規劃（Sparse node Dynamic Programming， SDP）算法因為貪心選擇不當反而比BDP效果更差。

如在實際問題中，若第i個項集中的物品3i，3i+1，3i+2中，不止一個物品的價值密度遠超過非完整項的價值密度，不妨令p3i/w3i≥p3i+2/w3i+2pb/wb，此時GROA相對于NGROA最小損失價值（Minimum Loss Value， MLV）為：

其中，p3i+2-p3i是選擇價值密度最大而非價值最大直接損失的價值，w3i+2-w3i為該選擇情況下空余的背包承重，又因為空余的背包承重將從不超過非完整項價值密度的物品中選擇，所以將空出背包承重乘以非完整項的價值密度，即為GROA相對NGROA的MLV。

程序后在算法FCI中，首先利用第1）～4）步求得問題規模并對物品按照價值密度排序，生成物品個體編碼X及項集向量Y。然后利用第5）～27）步對問題進行貪心求解，其中第6）步為選取當前價值密度最大項。第7）～13）步判斷該物品所在項集是否有其他物品被選擇，如果物品所在項集沒有物品被選擇且選取該物品后背包內所有物品質量不超出背包承重，則選擇該物品。第15）～26）步表示，若物品所在項集已有選擇的物品，則按照NGROA思想，判斷該物品是否為當前項集中價值最大的物品，再對其進行背包載重測試，若未超出背包載重，則選擇該物品。最后通過第28）～29）步得到結果。

3 GCADP算法

動態規劃（Dynamic Programming， DP）由Bellman[19]基于貝爾曼最優性原理提出，廣泛用于求解NP問題。因DP能夠處理多階段決策問題，所以在離散系統、連續系統等領域都應用廣泛。利用DP求解各類背包問題算法相對較成熟[20-23]，故本文基于DP算法，結合核算法，提出GCADP對D{0-1}KP進行求解。

3.1 DP求解{0-1}KP

對于規模為n，背包容量為C的{0-1}KP，物品價值與質量分別為P，W。{0-1}KP[3，24-25]可描述為：

求解{0-1}KP，即找到最優向量X，使得目標函數值最大。利用DP求解{0-1}KP，首先定義V（n，C）的矩陣。對于2≤i≤n，1≤j≤C此處感覺描述有問題，是否應該改為“i，j，1≤i≤n，1≤j≤C”，注意是1≤i≤n，不是2≤i≤n。請明確?；貜停翰恍枰薷模琕v（i， j）此處的V（i， j），是否應該是一個具體的數值，而不是一個矩陣？請明確。要注意矩陣與矩陣中的具體數值的書寫問題，若是具體數據，V不應該是加黑加斜體。另外，其他處也存在此類現象。表示當前背包容量為j時，前i個物品組合對應的最大價值。算法迭代公式如下：

通過迭代計算，最終得到的V（n，C）即為問題的解。

3.2 BDP求解D{0-1}KP

BDP[5]求解D{0-1}KP與DP求解{0-1}KP算法思路類似，但在具體最優選擇上有較大不同。在傳統“一行一物”的標準，變為一行一項集。BDP算法迭代公式如下。

對于初始值設定為如下：

對于第2個項集至最后一個項集設定迭代公式如下：

對于D{0-1}KP模型，設價值系數集為P、重量系數W和背包載重容量C。因文獻[5]未給出算法偽代碼，對BDP算法Matlab偽代碼描述如算法2。

程序BDP算法中，首先利用第1）～3）步處理參數，第4）～7）步刻畫式（11），設置動態規劃第一行物品選取。第8）～19）步利用動態規劃法求解問題，其中第9）步表示該項集無任何物品可供選擇，直接繼承上一行結果，第10）～12）步表示該項集是否選擇第一個物品（質量和價值均最?。?3）～15）步表示該項集是否選擇第一、二個物品，第16）～18）步表示在該項集是否選擇物品。最后再輸出結果。

3.3 GCADP求解D{0-1}KP

GCADP算法在傳統SDP算法[5]基礎上，選擇NGROA作為貪心策略的動態規劃算法。因文獻[5]中已經經過實例論證SDP若弱于BDP，因此本文不再過多敘述SDP相關部分。GCADP與BDP類似，仍然以物品項集數量作為迭代行，每行通過w3i，w3i+1，w3i+2將區間[0，C]劃分為4個連續區間，分別為：[0，w3i），[w3i，w3i+1），[w3i+1，w3i+2）和[w3i+2，C]。并在迭代過程過程中，選擇物品價值最大的組合。GCADP算法迭代公式與BDP算法相同，不過多考慮。GCADP算法Matlab偽代碼描述如算法3。

程序后GCADP算法中，第1）～2）步分別得到問題規模及項集規模。第3）步通過FCI算法得到問題的模糊核區間。第4）～12）步為處理經過核算法處理過后的數據，其中第4）步是確認模糊核區間內的物品序號，第5）步確定核內物品所在項集，第6）步去除核內重復的項集，第7）～8）步將核內物品及其所在項集內的物品一起選出，第9）步是確定解空間的子空間{X1=1}，第10）步計算確定選擇的物品質量，第11）步為經過核算法計算后，處理還需計算的數據，第12）步計算還需求解的項集個數。第13）～29）步為DP算法求解，與BDP類似，不再過多闡述。最后輸出結果。

4 實例計算與結果對比

4.1 四類實例

因GCADP算法主要與BDP算法進行對比，但文獻[5]未公布實例數據，因此采用文獻[3]中數據進行求解。

文獻[3]按照數據關系分為四類，分別是不相關D{0-1}KP實例（Uncorrelated instances of D{0-1}KP， UDKP）、弱相關D{0-1}KP實例（Weakly instances of D{0-1}KP， WDKP）、強相關D{0-1}KP實例（Strongly correlated instances of D{0-1}KP， SDKP）和逆向強相關實例（Inverse strongly correlated instances of D{0-1}KP， IDKP）[5-6，26]，具體內容可參考文獻[5-6，26]，此處限于篇幅，不再贅述。

值得注意的是，考慮到D{0-1}KP與傳統{0-1}KP的區別，尤其是D{0-1}KP每個項集中存在三個物體，因而考慮設置與標準核半徑不同，令r=3n，通過后續實際算例驗證此時核半徑能夠對問題求解得到精確解。

本文所使用工作站為Dell Precision-T1700，操作系統為Windows 10專業版，硬件配置為Intel Xeon CPU E3-1241 V3@3.50GHz，8.00GB RAM（5.7GB空余）。

4.2 求解結果及比對

分別利用BDP、GCADP和FirEGA（First Elitist reservation strategy Genetic Algorithm）對四類算例進行求解。因BDP和GCADP兩種算法均為非隨機性算法，輸出結果穩定。記BDP其結果為Opt1，計算時長為T1;GCADP其結果為Opt2，計算時長為T2。FirEGA為遺傳算法30次獨立計算結果的最優解。其中，Best為30次獨立計算最優解集合中的最大值，類比可知，Mean為平均值，Worst為最差值，計算總時長為T3。T1、T2、T3的單位為s。又BDP能夠對問題進行精確求解，而GCADP未能對問題進行全局搜索，故設置誤差率（Error Rate， ER），計算方式為：ER=1-Opt2/Opt1。對于求解速度，設定IT1作為提升效果，其計算公式為：IT1=（T2-T1）/T2，類比IT1，IT2=（T3-T1）/T3。通過實際計算得到結果如表1。

從表1中可以看出：GCADP的誤差在可接受范圍內，在WDKP等三類實例計算中，誤差率均低于0.10%，雖然在UDKP實例中誤差最大為0.57%，但和當前其他求解折扣背包問題的群智能算法相比，結果誤差可接受，且性能優秀。

而對于求解時長來看，結合表1，GCADP算法隨著算例規模增大，求解時長增長緩慢，相對于BDP隨著問題規模呈指數型增長，則無疑優勢明顯。

從表1可知，GCADP提升效果明顯，并呈現出隨著算例規模的增大，提升效果越明顯。綜合來看，相對BDP，求解提升平均效果為76.24%，相對FirEGA，提升平均效果為75.07%，整體效果理想。

5 結語

本文通過改進SDP中貪心選擇策略，從GROA策略更改為NGROA，進而提出GCADP算法求解D{0-1}KP。數據結果表明：GCADP不僅在求解速度上快速提高，且問題的求解精度也更優秀?？傮w而言，因為GCADP正確的貪心選擇策略，使得求解精度與速度能夠有效提高，是一種性能優良的加速算法，但是，相對于BDP而言，GCADP需要增添核半徑r參數。雖然通過擴大核半徑r的數值可以使得結果更優秀，但求解時長大幅度增加，得不償失，但GCADP在對于IDKP的實例求解中，能夠確保得到UDKP的精確解，則接下來不妨考慮UDKP與其余三類數據的差異性，并對貪心策略進行針對性修改，從而使得加速算法能夠對問題進行精確求解。

參考文獻 （References）

[1] GUDER J. Discounted knapsack problems for pairs of items [D]. Nuremberg： University of Erlangen-Nurnberg， 2005.

[2] GULDAN B. Heuristic and exact algorithms for discounted knapsack prob1ems[D]. Nuremberg： University of Erlangen-Nuremberg， 2007.

[3] 賀毅朝，王熙照，李文斌，等.基于遺傳算法求解折扣{0-1}背包問題的研究[J].計算機學報，2016，39（12）：2614-2630.（HE Y C， WANG X Z， Ll W B， et al. Research on genetic algorithms for the discounted {0-1} knapsack problem[J]. Chinese Journal of Computers， 2016， 39（12）： 2614-2630.）

[4] 楊洋，潘大志，劉益，等.折扣{0-1}背包問題的簡化新模型及遺傳算法求解[J].計算機應用，2019，39（3）：656-662.（YANG Y， PAN D Z， LIU Y， et al. New simplified model of discounted {0-1} knapsack problem and solution by genetic algorithm[J]. Journal of Computer Applications， 2019， 39（3）： 656-662.）

[5] RONG A Y， FIGUEIRA J R， KLAMROTH K. Dynamic programming based algorithms for the discounted {0-1} knapsack problem[J]. Applied Mathematics and Computation， 2012， 218（12）： 6921-6933.

[6] HE Y C， WANG X Z， HE Y L， et al. Exact and approximate algorithms for discounted {0-1} knapsack problem[J]. Information Sciences， 2016， 369（10）： 634-647.

[7] 楊洋，潘大志，賀毅朝.改進修復策略遺傳算法求解折扣{0-1}背包問題[J].計算機工程與應用，2018，54（21）：37-42.（YANG Y， PAN D Z， HE Y C. Improved repair strategy genetic algorithm solve discount {0-1} knapsack problem[J]. Computer Engineering and Applications， 2018， 54（21）：37-42.）

[8] 楊洋，潘大志，賀毅朝.核加速遺傳算法求解折扣{0-1}背包問題[J].西華師范大學學報（自然科學版），2018，39（2）：165-172.（YANG Y， PAN D Z， HE Y C. Core accelerated genetic algorithm to solve the discount {0-1} knapsack problem[J].Journal of China West Normal University （Natural Sciences edition）， 2018， 39（2）： 165-172.）

[9] FENG Y H， WANG G G， LI W， et al. Multi-strategy monarch butterfly optimization algorithm for discounted {0-1} knapsack problem[J]. Neural Computing and Applications， 2018， 30（10）： 3019-3016.

[10] 馮艷紅，楊娟，賀毅朝，等.差分進化帝王蝶優化算法求解折扣{0-1}背包問題[J].電子學報，2018，46（6）：1343-1350.（FENG Y H， YANG J， HE Y C， et al. Monarch butterfly optimization algorithm with differential evolution for the discounted {0-1} knapsack problem[J]. Acta Electronica Sinica， 2018， 46（6）： 1343-1350.）

[11] FENG Y H， WANG G G. Binary moth search algorithm for discounted {0-1} knapsack problem[J]. IEEE Access， 2018， 6： 10708-10719.

[12] 劉雪靜，賀毅朝，路鳳佳，等.基于Lévy飛行的差分烏鴉算法求解折扣{0-1背包問題[J].計算機應用，2018，38（2）：433-442.（LIU X J， HE Y C， LU F J， et al. Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem [J]. Journal of Computer Applications， 2018， 38（2）： 433-442.）

[13] 劉雪靜，賀毅朝，路鳳佳，等.基于差分演化策略的混沌烏鴉算法求解折扣{0-1}背包問題[J].計算機應用，2018，38（1）：137-145.（LIU X J， HE Y C， LU F J， et al. Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem[J]. Journal of Computer Applications， 2018， 38（1）： 137-145.）

[14] 吳聰聰，賀毅朝，陳嶷瑛，等.變異蝙蝠算法求解折扣{0-1}背包問題[J].計算機應用，2017，37（5）：1292-1299.（WU C C， HE Y C， CHEN Y Y， et al. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications， 2017， 37（5）： 1292-1299.）

[15] 劉雪靜，賀毅朝，吳聰聰，等.基于細菌覓食算法求解折扣{0-1}背包問題的研究[J].計算機工程與應用，2018，54（2）：155-162.（LIU X J， HE Y C， WU C C， et al. Research on bacterial foraging optimization algorithm for discounted {0-1} knapsack problem[J]. Computer Engineering and Applications， 2018， 54（2）： 155-162.）

[16] BALAS E， ZEMEL E. An algorithm for large zero-one knapsack problems[J]. Operations Research， 1980， 28（5）： 1130-1154.

[17] PISINGER D. Core problems in knapsack algorithms[J]. Operations Research， 1999， 47（4）： 570-575.

[18] PISINGER D. An expanding-core algorithm for the exact 0-1 knapsack problem[J]. European Journal of Operational Research， 1995， 87（1）： 175-187.

[19] BELLMAN R. Dynamic programming[J]. Science， 1966， 153（3731）： 34-37.

[20] MARTELLO S， PISINGER D， TOTH P. Dynamic programming and strong bounds for the 0-1 knapsack problem[J]. Management Science， 1999， 45（3）： 414-424.

[21] KATHRIN K， WIECEK M M. Dynamic programming approaches to the multiple criteria knapsack problem[J]. Naval Research Logistics， 2015， 47（1）： 57-76.

[22] BALEV S， YANEV N， FREVILLE A， et al. A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem[J]. European Journal of Operational Research， 2008， 186（1）： 63-76.

[23] DYER M E， RIHA W O， WALKER J. A hybrid dynamic programming/branch-and-bound algorithm for the multiple-choice knapsack problem[J]. Journal of Computational and Applied Mathematics， 1995， 58（1）： 43-54.

[24] MARTELLO S， TOTH P. Knapsack problems： algorithms and computer implementations[J]. Journal of the Operational Research Society， 1991， 42（6）： 513-513.

[25] GAREY M R， JOHNSON D S， STOCKMEYER L. Some simplified NP-complete graph problems[J]. Theoretical Computer Science， 1976， 1（3）： 237-267.

[26] KELLERER H， PFERSCHY U， PISINGER D. Knapsack Problems[M]. Berlin： Springer， 2004： 1-17.