貪心核加速動態(tài)規(guī)劃算法求解折扣{0-1}背包問題

史文旭 楊洋 鮑勝利

摘 要：針對現(xiàn)有動態(tài)規(guī)劃算法求解折扣{0-1}背包問題（D{0-1}KP）緩慢的問題，基于動態(tài)規(guī)劃思想并結(jié)合新型貪心修復(fù)優(yōu)化算法（NGROA）與核算法，通過縮小問題規(guī)模加速問題求解來提出一種貪心核加速動態(tài)規(guī)劃（GCADP）算法。首先利用NGROA對問題進(jìn)行貪心求解，得到非完整項(xiàng);然后通過計(jì)算得到模糊核區(qū)間的半徑和模糊核區(qū)間范圍;最后對于模糊核區(qū)間內(nèi)的物品及同一項(xiàng)集內(nèi)的物品利用基礎(chǔ)動態(tài)規(guī)劃（BDP）算法求解。實(shí)驗(yàn)結(jié)果表明：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）是經(jīng)典的{0-1}背包問題（{0-1} Knapsack Problem，{0-1}KP）的一個(gè)拓展形式[1-6]，通過數(shù)學(xué)模型刻畫實(shí)際商業(yè)活動中折扣銷售、捆綁銷售等現(xiàn)象，對這類問題進(jìn)行最優(yōu)化求解，達(dá)到獲利最大化。D{0-1}KP可簡單理解為A物品售價(jià)40元，B物品售價(jià)50元，同時(shí)購買A，B記為購買物品C只需支出80元或其他小于90元的價(jià)格。在現(xiàn)實(shí)商業(yè)銷售案例中，如“黑色星期五”“雙十一”等大型購物節(jié)，通過D{0-1}KP能夠很好地使客戶在項(xiàng)目決策得到最優(yōu)方案，銷售商也能夠通過D{0-1}KP更有針對性地設(shè)計(jì)自己的銷售方案。利用D{0-1}KP使得商業(yè)價(jià)值達(dá)到最大化，在實(shí)際商業(yè)問題中，具有廣闊的應(yīng)用前景。

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

對于D{0-1}KP的求解算法方面，主要有精確算法求解及群智能算法求解兩大方面。對于精確算法，主要是基于動態(tài)規(guī)劃算法，如Rong等[5]結(jié)合背包問題中的核問題對D{0-1}KP提出了基于核問題的基礎(chǔ)動態(tài)規(guī)劃（Basic Dynamic Programming， BDP）等。He等[6]通過對偶思想，將動態(tài)規(guī)劃中最大價(jià)值轉(zhuǎn)換為求解最小質(zhì)量，提出針對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]等成果。

基于文獻(xiàn)[7]中提出的新型貪心修復(fù)優(yōu)化算法（New Greedy Repaired Optimization Algorithm， NGROA），通過核算法[8]縮小問題規(guī)模，加速問題求解，再利用動態(tài)規(guī)劃算法對問題進(jìn)行求解，提出貪心核加速動態(tài)規(guī)劃（Greedy Core Acceleration Dynamic Programming， GCADP）算法。利用GCADP求解四類大規(guī)模D{0-1}KP實(shí)例，分析其結(jié)果。

2 改進(jìn)核算法

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

2.1 精確核算法

對于{0-1}KP而言，核算法可理解為對于物品規(guī)模為n的解空間X1×n分為三個(gè)子空間的直和，即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即為精確核算法的解，也即核區(qū)間，接下來只需對X2進(jìn)一步求解即可，則將問題規(guī)模從dim（X1×n）=n縮減為dim（X21×n2）=n2，從而達(dá)到加速的效果。

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

2.2 近似核算法

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

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

2.3 貪心策略

D{0-1}KP與{0-1}KP在利用貪心思想求解近似解時(shí)，最大的不同便在于D{0-1}KP在選擇當(dāng)前價(jià)值密度最大項(xiàng)時(shí)，會出現(xiàn)同一項(xiàng)集內(nèi)的多個(gè)物品同時(shí)被選擇的情況。傳統(tǒng)貪心修復(fù)優(yōu)化算法（Greedy Repaired Optimization Algorithm， GROA）在處理這類問題時(shí)，選擇價(jià)值密度最大項(xiàng)。目標(biāo)函數(shù)并非是選擇價(jià)值密度最大項(xiàng)，而是價(jià)值最大項(xiàng)。這就導(dǎo)致文獻(xiàn)[5]中，結(jié)合核算法的稀疏點(diǎn)動態(tài)規(guī)劃（Sparse node Dynamic Programming， SDP）算法因?yàn)樨澬倪x擇不當(dāng)反而比BDP效果更差。

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

其中，p3i+2-p3i是選擇價(jià)值密度最大而非價(jià)值最大直接損失的價(jià)值，w3i+2-w3i為該選擇情況下空余的背包承重，又因?yàn)榭沼嗟谋嘲兄貙牟怀^非完整項(xiàng)價(jià)值密度的物品中選擇，所以將空出背包承重乘以非完整項(xiàng)的價(jià)值密度，即為GROA相對NGROA的MLV。

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

3 GCADP算法

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

3.1 DP求解{0-1}KP

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

求解{0-1}KP，即找到最優(yōu)向量X，使得目標(biāo)函數(shù)值最大。利用DP求解{0-1}KP，首先定義V（n，C）的矩陣。對于2≤i≤n，1≤j≤C此處感覺描述有問題，是否應(yīng)該改為“i，j，1≤i≤n，1≤j≤C”，注意是1≤i≤n，不是2≤i≤n。請明確?；貜?fù)：不需要修改，Vv（i， j）此處的V（i， j），是否應(yīng)該是一個(gè)具體的數(shù)值，而不是一個(gè)矩陣？請明確。要注意矩陣與矩陣中的具體數(shù)值的書寫問題，若是具體數(shù)據(jù)，V不應(yīng)該是加黑加斜體。另外，其他處也存在此類現(xiàn)象。表示當(dāng)前背包容量為j時(shí)，前i個(gè)物品組合對應(yīng)的最大價(jià)值。算法迭代公式如下：

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

3.2 BDP求解D{0-1}KP

BDP[5]求解D{0-1}KP與DP求解{0-1}KP算法思路類似，但在具體最優(yōu)選擇上有較大不同。在傳統(tǒng)“一行一物”的標(biāo)準(zhǔn)，變?yōu)橐恍幸豁?xiàng)集。BDP算法迭代公式如下。

對于初始值設(shè)定為如下：

對于第2個(gè)項(xiàng)集至最后一個(gè)項(xiàng)集設(shè)定迭代公式如下：

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

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

3.3 GCADP求解D{0-1}KP

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

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

4 實(shí)例計(jì)算與結(jié)果對比

4.1 四類實(shí)例

因GCADP算法主要與BDP算法進(jìn)行對比，但文獻(xiàn)[5]未公布實(shí)例數(shù)據(jù)，因此采用文獻(xiàn)[3]中數(shù)據(jù)進(jìn)行求解。

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

值得注意的是，考慮到D{0-1}KP與傳統(tǒng){0-1}KP的區(qū)別，尤其是D{0-1}KP每個(gè)項(xiàng)集中存在三個(gè)物體，因而考慮設(shè)置與標(biāo)準(zhǔn)核半徑不同，令r=3n，通過后續(xù)實(shí)際算例驗(yàn)證此時(shí)核半徑能夠?qū)栴}求解得到精確解。

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

4.2 求解結(jié)果及比對

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

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

而對于求解時(shí)長來看，結(jié)合表1，GCADP算法隨著算例規(guī)模增大，求解時(shí)長增長緩慢，相對于BDP隨著問題規(guī)模呈指數(shù)型增長，則無疑優(yōu)勢明顯。

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

5 結(jié)語

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

參考文獻(xiàn) （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].計(jì)算機(jī)學(xué)報(bào)，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].計(jì)算機(jī)應(yīng)用，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] 楊洋，潘大志，賀毅朝.改進(jìn)修復(fù)策略遺傳算法求解折扣{0-1}背包問題[J].計(jì)算機(jī)工程與應(yīng)用，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].西華師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 馮艷紅，楊娟，賀毅朝，等.差分進(jìn)化帝王蝶優(yōu)化算法求解折扣{0-1}背包問題[J].電子學(xué)報(bào)，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].計(jì)算機(jī)應(yīng)用，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].計(jì)算機(jī)應(yīng)用，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].計(jì)算機(jī)應(yīng)用，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] 劉雪靜，賀毅朝，吳聰聰，等.基于細(xì)菌覓食算法求解折扣{0-1}背包問題的研究[J].計(jì)算機(jī)工程與應(yīng)用，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.