史文旭 楊洋 鮑勝利

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

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

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

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

2 改進(jìn)核算法

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

2.1 精確核算法

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

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

2.2 近似核算法

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

X∈{0，1}1×n表示為該背包問(wè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為問(wèn)題規(guī)模;N為自然數(shù)集。

2.3 貪心策略

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

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

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

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

3 GCADP算法

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

3.1 DP求解{0-1}KP

對(duì)于規(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）的矩陣。對(duì)于2≤i≤n，1≤j≤C此處感覺(jué)描述有問(wèn)題，是否應(yīng)該改為“i，j，1≤i≤n，1≤j≤C”，注意是1≤i≤n，不是2≤i≤n。請(qǐng)明確?；貜?fù)：不需要修改，Vv（i， j）此處的V（i， j），是否應(yīng)該是一個(gè)具體的數(shù)值，而不是一個(gè)矩陣？請(qǐng)明確。要注意矩陣與矩陣中的具體數(shù)值的書(shū)寫(xiě)問(wèn)題，若是具體數(shù)據(jù)，V不應(yīng)該是加黑加斜體。另外，其他處也存在此類(lèi)現(xiàn)象。表示當(dāng)前背包容量為j時(shí)，前i個(gè)物品組合對(duì)應(yīng)的最大價(jià)值。算法迭代公式如下：

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

3.2 BDP求解D{0-1}KP

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

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

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

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

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

3.3 GCADP求解D{0-1}KP

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

程序后GCADP算法中，第1）～2）步分別得到問(wèn)題規(guī)模及項(xiàng)集規(guī)模。第3）步通過(guò)FCI算法得到問(wèn)題的模糊核區(qū)間。第4）～12）步為處理經(jīng)過(guò)核算法處理過(guò)后的數(shù)據(jù)，其中第4）步是確認(rèn)模糊核區(qū)間內(nèi)的物品序號(hào)，第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)過(guò)核算法計(jì)算后，處理還需計(jì)算的數(shù)據(jù)，第12）步計(jì)算還需求解的項(xiàng)集個(gè)數(shù)。第13）～29）步為DP算法求解，與BDP類(lèi)似，不再過(guò)多闡述。最后輸出結(jié)果。

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

4.1 四類(lèi)實(shí)例

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

文獻(xiàn)[3]按照數(shù)據(jù)關(guān)系分為四類(lèi)，分別是不相關(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，通過(guò)后續(xù)實(shí)際算例驗(yàn)證此時(shí)核半徑能夠?qū)?wèn)題求解得到精確解。

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

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

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

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

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

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

5 結(jié)語(yǔ)

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