代祖華，劉園園，狄世龍，樊琦

西北師范大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，蘭州730070

{0-1}背包問題（{0-1} knapsack problem，{0-1}KP）是計算機(jī)科學(xué)一個重要的NP Complete 問題，也是一類經(jīng)典組合優(yōu)化問題，在商業(yè)、經(jīng)濟(jì)、管理、安全等領(lǐng)域有著廣泛的應(yīng)用背景。{0-1}KP 自被提出后的幾十年里被反復(fù)地研究，衍生出精確算法、非精確算法兩大類算法。精確算法有動態(tài)規(guī)劃、回溯法和分支限界法等；非精確算法主要有隨機(jī)算法、近似算法、生物算法等。在目前求解{0-1}KP 的各類算法中，基于核概念[1]的算法被認(rèn)為是處理大規(guī)模{0-1}KP 的有效算法[2]。2005 年，由Guder 首次提出的折扣{0-1}背包問題[3-4]（discounted {0-1} knapsack problem，D{0-1}KP）是{0-1}背包問題的拓展形式，作為刻畫折扣銷售、捆綁銷售等商業(yè)活動現(xiàn)象的經(jīng)典數(shù)學(xué)模型，是商家設(shè)計商業(yè)營銷方案、消費者購買商品決策的科學(xué)計算依據(jù)。

D{0-1}KP 實例由一組項集組成，每個項集有3項物品可供背包裝入選擇，其中第三項物品價值是前兩項之和，第三項物品重量小于其他兩項之和，算法求解中如果選擇了某個項集，則需要確定選擇項集的哪個項。因此，D{0-1}KP 的項集有4 種選擇狀態(tài)。另外，如果背包的容量和項的價值系數(shù)取值范圍很大，則不選擇某個項集的約束條件較難確定，這意味D{0-1}KP 的算法難度要大于{0-1}KP[5]。以{0-1}KP 研究成果為基礎(chǔ)，學(xué)者們進(jìn)一步研究了D{0-1}KP 的各類算法。其中基礎(chǔ)動態(tài)規(guī)劃算法（basic dynamic programming，BDP）[4]是處理小規(guī)模數(shù)據(jù)的精確解算法，由于動態(tài)規(guī)劃算法是偽多項式時間復(fù)雜度，一般不適用于大規(guī)模D{0-1}KP 實例的求解；2016 年，He 等人[6]以“所選擇項的價值系數(shù)之和使總重量最小”原則構(gòu)造動態(tài)規(guī)劃目標(biāo)函數(shù)，提出一種新動態(tài)規(guī)劃算法（new exact algorithm for D{0-1}KP，NEDKP）。當(dāng)背包容量大于項集第三項價值累加和時，新算法性能好于BDP。粒子群算法[6]、遺傳算法[7-8]、猴群算法[9]、教與學(xué)優(yōu)化算法[10]是近年來提出求解D{0-1}KP 的群智能算法，作為啟發(fā)式算法，需要通過數(shù)據(jù)仿真實驗調(diào)控算法參數(shù)，求解結(jié)果具有不確定性。2012 年，Rong等人[5]以{0-1}KP 核概念[1]為基礎(chǔ)研究了D{0-1}KP 的核（Core）問題，基于核區(qū)間將原問題劃分為3 個約簡子問題，提出一種基于核區(qū)間劃分的D{0-1}KP 分治算法。研究結(jié)果表明，對于多數(shù)類型的D{0-1}KP 數(shù)據(jù)，采用分治求解策略的動態(tài)規(guī)劃算法效率要高于對原問題直接求解。2018 年，楊洋等人將貪心核區(qū)間算法與遺傳算法進(jìn)行融合，提出求解D{0-1}KP 的核加速遺傳算法（core acceleration genetic algorithm，CEGA）[8]。2019 年，史文旭等人將模糊核區(qū)間算法與動態(tài)規(guī)劃算法相結(jié)合，提出了貪心核加速動態(tài)規(guī)劃算法（greedy core acceleration dynamic programming，GCADP）[11]。與啟發(fā)式算法相比，基于核區(qū)間估計的D{0-1}KP 近似算法求解結(jié)果穩(wěn)定，算法需要調(diào)控參數(shù)較少，值得進(jìn)一步優(yōu)化與改進(jìn)。

求解D{0-1}KP 問題的精確核區(qū)間是一個NPC問題，現(xiàn)有文獻(xiàn)[5,8,11]研究了D{0-1}KP 基于近似核區(qū)間的求解算法，思路是：首先按物品價值密度對數(shù)據(jù)進(jìn)行非遞增排序，然后利用貪心算法選取不完整項集b，以b為中心估算近似核區(qū)間[s,t]。不同于{0-1}KP，D{0-1}KP 的核區(qū)間以b為中心非對稱分布，且分布區(qū)間與數(shù)據(jù)實例類型相關(guān)[5]。本文發(fā)現(xiàn)：近似核區(qū)間算法需按物品價值密度進(jìn)行非遞增排序，{0-1}KP 只有一種排序方案，而D{0-1}KP 每個項集有3項，故存在多種排序方案。文獻(xiàn)[5]認(rèn)為項集的第三項比其他兩項更有優(yōu)勢，故選擇第三項價值密度作為項集排序數(shù)據(jù)，不打亂項集的項次序；文獻(xiàn)[6-8,11-12]則將所有項按項價值密度非遞增排序，并利用項集排序序號數(shù)組轉(zhuǎn)錄源數(shù)據(jù)，算法需處理一個項集中多個項被選取的非正常情況。本文在研究{0-1}KP核概念基礎(chǔ)上，修正了文獻(xiàn)[5]的D{0-1}KP 核區(qū)間定義，提出一種可顯著縮減核區(qū)間規(guī)模的分段排序策略和貪心核算法，設(shè)計了D{0-1}KP 基于分段排序貪心核的動態(tài)規(guī)劃核加速算法。

1 D{0-1}KP 數(shù)學(xué)模型與算法

1.1 D{0-1}KP 數(shù)學(xué)模型

D{0-1}KP 是一個特殊整數(shù)規(guī)劃問題，定義決策變量xj=1(0 ≤j≤3n-1)表示項j裝入背包，xj=0 表示項j未裝入背包，對于決策向量(x0,x1,…,x3n-1)，D{0-1}KP 的整數(shù)規(guī)劃模型為：

1.2 D{0-1}KP 問題的核算法

定義2（D{0-1}KP 不完整項集b）對D{0-1}KP的n個項集，按其第三項價值密度以非遞增序列排序，貪心選擇每個項集第三項裝入背包，直至裝入背包的累計重量超出背包容量C的首個項集序號即為b，b滿足：

D{0-1}KP 每個項集有4 個選擇，導(dǎo)致{0-1}KP 的核區(qū)間定義不能直接應(yīng)用于D{0-1}KP。文獻(xiàn)[5]專門研究了D{0-1}KP 的核劃分方案。具體做法是：對所有項集按第三項價值密度以非遞增序列排序后，若x*是給定D{0-1}KP 的最優(yōu)解，定義D{0-1}KP 的核區(qū)間為CI=[g1,g2]，其中：

D{0-1}KP 核區(qū)間位置通常在不完整項集序號b附近，核區(qū)間規(guī)模與數(shù)據(jù)實例類型相關(guān)。利用式（2）定義核區(qū)間可將原問題劃分為式（3）所示區(qū)間上的三個子問題。

1.3 D{0-1}KP 動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法（dynamic programming，DP）是Bellman 提出的一種多階段決策最優(yōu)化求解算法，也是求解各類{0-1}KP 問題的經(jīng)典算法[16]。文獻(xiàn)[5]提出求解D{0-1}KP 的標(biāo)準(zhǔn)動態(tài)規(guī)劃算法（BDP）：定義階段變量i∈[0,n-1]對應(yīng)BDP 求解過程中項集的選擇編號范圍上界；定義狀態(tài)變量j∈[0,C]對應(yīng)BDP 求解中背包可能的剩余載重量，v(i,j)表示算法在第i階段背包剩余載重量為j的狀態(tài)下可裝入背包的最大價值，則v(0,j)保存v(i,j)的初始值，表示可選擇項集為第一個項集的局部最優(yōu)值，可按照式（7）賦值。計算其余v(i,j) 的決策狀態(tài)轉(zhuǎn)移方程如式（8），最終，D{0-1}KP 的最優(yōu)價值可從v(n-1,C)中獲取，不難推斷BDP 算法時間復(fù)雜度為O(nC)。

BDP 算法的小規(guī)模D{0-1}KP 數(shù)據(jù)集最優(yōu)解表明：項集的第三個項占背包裝入必選項的大部分，按項集第三項價值密度對數(shù)據(jù)非遞增排序后，BDP 算法得到的最優(yōu)解x*和貪心算法得到的不完整解x′僅在不完整項b附近的少量項集取值上有差異，這些項集即為核區(qū)間覆蓋項集。D{0-1}KP 的核區(qū)間算法方案是：貪心選擇項集第三項確定不完整項位置b，然后以b為中心非對稱擴(kuò)展核區(qū)間項集，確保核區(qū)間覆蓋項集可以獲得較優(yōu)解項集。

定義3（受控狀態(tài)）用sα(t)表示動態(tài)規(guī)劃α階段中重量-價值對(t,gα(t)) 對應(yīng)的狀態(tài)，若有t1

根據(jù)受控狀態(tài)的定義，BDP 算法在求解各個階段有許多冗余狀態(tài)組成，這些狀態(tài)對于計算最優(yōu)解無用，稀疏點動態(tài)規(guī)劃算法（sparse node DP，SDP）通過丟棄受控狀態(tài)來減少冗余狀態(tài)，SDP 算法的狀態(tài)數(shù)與物品重量與價值的數(shù)據(jù)分布有關(guān)。為減少SDP 算法處理丟棄受控狀態(tài)的算法耗費，LDP 算法減少了SDP 算法中受控狀態(tài)的丟棄數(shù)量，LDP 算法的狀態(tài)數(shù)只與物品的重量分布有關(guān)。文獻(xiàn)[5]的數(shù)據(jù)實驗結(jié)果表明，核區(qū)間加速算法SDP、LDP 算法由于篩選丟棄動態(tài)規(guī)劃過程冗余狀態(tài)的計算耗費過大，在大規(guī)模數(shù)據(jù)情況下性能比BDP 算法更差。

2 D{0-1}KP 之分段排序貪心核算法

2.1 D{0-1}KP 核區(qū)間修正定義

為解決式（2）核區(qū)間定義存在的問題，本文提出D{0-1}KP 的修正核區(qū)間CI定義，如式（9）所示：

易見式（9）確定的CI=CI12∪CI2∪CI31，采用分治策略求解時，原問題可分為三個子問題：第一個子問題由選擇第三項的必選項集組成；第二個子問題是背包容量減小的原問題；第三個子問題由不選擇項集組成。與式（2）核區(qū)間定義相比，式（9）定義的核區(qū)間擴(kuò)增了CI12與CI31，但可有效解決式（2）對部分?jǐn)?shù)據(jù)實例的可能存在的核區(qū)間劃分不合理問題，故基于式（9）核區(qū)間的分治求解算法較之文獻(xiàn)[5]更為簡單，易于將原問題約簡為一個小規(guī)模子問題求解，有效提升近似算法性能。

為驗證兩種核區(qū)間定義的差異，本文構(gòu)造四種類型的D{0-1}KP 小規(guī)模數(shù)據(jù)實例，每個數(shù)據(jù)實例包括10 個規(guī)模不等的數(shù)據(jù)集，背包容量滿足，按項集第三項價值密度對項集非遞增排序，項集內(nèi)各項保持原有次序。即若用di表示項集i的價值密度有di=e3i+2，若i

數(shù)據(jù)排序后應(yīng)用貪心算法計算每個數(shù)據(jù)實例滿足式（1）的不完整項集編號b，用BDP 算法計算最優(yōu)解向量x*，分別按照式（2）和式（9）計算CI=[g1,g2]，為去除數(shù)據(jù)規(guī)模對實驗結(jié)果的影響，計算數(shù)據(jù)實例的b、g1、g2在排序數(shù)據(jù)的百分位序，如圖1、圖2所示。

圖1 的實驗結(jié)果驗證了文獻(xiàn)[5]核區(qū)間定義存在以下問題：數(shù)據(jù)實例的核區(qū)間邊界值可能出現(xiàn)g1>g2情況，例如圖1（c）在200、600、700 處的數(shù)據(jù)集藍(lán)色線條位于黑色線條上方；有些數(shù)據(jù)實例的核區(qū)間不包含不完整項b，如圖1（b）黃色線條未落在黑色、藍(lán)色線條之間。這些問題影響D{0-1}KP 的貪心核區(qū)間相關(guān)算法性能。從圖2 實驗結(jié)果看出，修正核區(qū)間從不完整項b開始向兩側(cè)擴(kuò)展，符合文獻(xiàn)[1]關(guān)于{0-1}KP 核區(qū)間定義基本要求，核區(qū)間呈非對稱分布；IDKP 類型數(shù)據(jù)實例的核區(qū)間規(guī)模最小，SDKP、WDKP 類型數(shù)據(jù)實例的核右側(cè)邊界g2近似為n，UDKP 類型數(shù)據(jù)實例的核區(qū)間接近原數(shù)據(jù)規(guī)模；核區(qū)間在不同規(guī)模數(shù)據(jù)集上跨度偏大，如圖2（a）的300、600 位置處，圖2（b）的300 位置處，圖2（d）的900 位置處等。

圖1 文獻(xiàn)[5]核區(qū)間定義計算結(jié)果Fig.1 Calculation results of definition of core in ref.[5]

圖2 修正核區(qū)間定義計算結(jié)果Fig.2 Calculation results of repaired core definition

2.2 D{0-1}KP 修正貪心核算法

與精確核區(qū)間記號[g1,g2]相區(qū)別，貪心核區(qū)間采用記號[s,t]表示。文獻(xiàn)[5]按數(shù)據(jù)規(guī)模分段給出了不同類型數(shù)據(jù)實例的貪心核區(qū)間經(jīng)驗值，其值與文中定義的精確核無顯著相關(guān)性。文獻(xiàn)[11]的貪心核算法如下：

考慮到D{0-1}KP 的核區(qū)間規(guī)模與數(shù)據(jù)類型相關(guān)，分析四類D{0-1}KP 實例生成的參數(shù)設(shè)置[7]看出，四類D{0-1}KP 實例之間的差異主要體現(xiàn)在項重量和項價值的數(shù)量關(guān)系不同，為此引入如式（11）的相關(guān)系數(shù)統(tǒng)計量以區(qū)分不同的四類數(shù)據(jù)實例。

采用類似文獻(xiàn)[5,11]的方法和圖2 修正核區(qū)間特征構(gòu)造D{0-1}KP 的貪心核區(qū)間（repaired greedy core interval，RGCI）[s,t]算法如式（12）～（15），式中常數(shù)為經(jīng)驗數(shù)值，b為不完整項序號，n表示數(shù)據(jù)規(guī)模，ρ為物品重量與價值的相關(guān)系數(shù)。

設(shè)計基于修正核區(qū)間定義的D{0-1}KP貪心核區(qū)間動態(tài)規(guī)劃加速算法（repaired greedy core acceleration dynamic programming algorithm，RGCADP）如下：

算法1RGCADP

算法1第2 步按項集第三項價值密度對項集的價值向量P和重量向量W進(jìn)行非遞增排序，第3～5步在排序后的P、W上執(zhí)行貪心算法計算b，第6 步按式（11）計算相關(guān)系數(shù)ρ，第7 步按項集類型type 選擇式（12）～（15）計算貪心核區(qū)間[s,t]，第8 步計算貪心核區(qū)間的剩余背包容量CR和[0,s-1]區(qū)間裝入背包的價值maxV，第9、10 步對子問題X[0,3s-1]、X[3(t+1),3n-1]賦值；第11 步采用BDP 算法求解核區(qū)間[s,t]的決策向量X[3s:3t+2]和最優(yōu)解maxVBDP，第12 步計算近似最優(yōu)解opt2。RGCADP 是一個具有偽多項式時間的近似算法，時間復(fù)雜度為O(n+nlbn+，與BDP 算法時間復(fù)雜度O(nC)相比，當(dāng)CR?C時，RGCADP 可有效縮減算法輸入數(shù)據(jù)規(guī)模而改善算法性能。

2.3 D{0-1}KP 的分段排序貪心核算法

D{0-1}KP 核區(qū)間規(guī)模與數(shù)據(jù)排序算法密切相關(guān)，為解決式（9）在部分?jǐn)?shù)據(jù)集上核區(qū)間規(guī)模較大問題，本文提出D{0-1}KP 分段排序算法。

算法2D{0-1}KP 分段排序算法（piecewise sort）

算法2第6 步對[b,n-1]區(qū)間的項集（數(shù)據(jù)包括價值和重量）按三項的最大價值密度值進(jìn)行非遞增排序，項集內(nèi)各項保持原有次序。易見D{0-1}KP 分段排序算法的時間復(fù)雜度為O(n+nlbn)。

采用BDP 算法對排序后數(shù)據(jù)計算最優(yōu)解向量x*，并按照式（9）計算CI=[g1,g2]，如圖3 所示。

對比圖2、圖3 實驗結(jié)果看出，D{0-1}KP 數(shù)據(jù)采用分段排序算法處理后，核區(qū)間CI的子區(qū)間[b,g2]規(guī)模顯著縮減。表1 給出采用分段排序算法的核區(qū)間CI數(shù)據(jù)規(guī)模占比率，表1 每類數(shù)據(jù)集有兩行數(shù)據(jù)，上一行數(shù)據(jù)表示[g1,b]的數(shù)據(jù)規(guī)模占比率，下一行數(shù)據(jù)表示(b,g2]的數(shù)據(jù)規(guī)模占比率。

利用圖3 和表1 的分段排序核區(qū)間特征，構(gòu)造D{0-1}KP的分段排序貪心核區(qū)間（greedy core interval based on piecewise sorting，GCI_PS）[s,t] 算法如式（16）～（19），式中常數(shù)為經(jīng)驗數(shù)值，b為不完整項序號，n表示數(shù)據(jù)規(guī)模，ρ為物品重量與價值的相關(guān)系數(shù)。

表1 分段排序算法的核區(qū)間數(shù)據(jù)規(guī)模占比率Table 1 Proportion of core interval data size based on piecewise sorting

圖3 基于分段排序的核區(qū)間Fig.3 Core interval based on piecewise sorting

應(yīng)用分段排序策略構(gòu)造D{0-1}KP 貪心核區(qū)間動態(tài)規(guī)劃加速算法（RGCADP based on piecewise sort，RGCADP_PS）如下：

算法3RGCADP_PS

算法3第1 步采用算法2 對項集分段排序，計算b，第6 步按項集類型type 選擇式（16）～（19）計算貪心核區(qū)間[s,t]。RGCADP_PS 與RGCADP 算法的時間復(fù)雜度均為，其中n是項集規(guī)模，[s,t]是貪心核區(qū)間，C是背包容量，w3i+2是項集第三項重量。與RGCADP 算法相比，RGCADP_PS 在項集的不完整項b處先后采用兩種排序策略而獲得更小規(guī)模貪心核和剩余背包容量而改善算法性能。

3 算法實驗分析與評價

D{0-1}KP 數(shù)據(jù)集是評測和觀察算法性能的標(biāo)準(zhǔn)數(shù)據(jù)集[7]，由IDKP、SDKP、WDKP 和UDKP 四類數(shù)據(jù)組成，每類數(shù)據(jù)包含10 個項集規(guī)模不同的實例，按類型分別命名為IDKP1～I(xiàn)DKP10、SDKP1～SDKP10、UDKP1～UDKP10、WDKP1～WDKP10，10 個數(shù)據(jù)實例的項集規(guī)模n∈{100,200,…,1 000}。為驗證D{0-1}KP 分段排序貪心核算法性能，本文采用BDP[5]、NEDKP[6]、RGCADP、RGCADP_PS、GCADP[11]、PSOGRDKP（particle swarm optimization based greedy repair algorithm for D{0-1}KP）[6,10]6 種算法求解D{0-1}KP 標(biāo)準(zhǔn)數(shù)據(jù)集，比較求解時間和解計算結(jié)果以分析RGCADP_PS 的性能。其中BDP 與NE-DKP 是精確解算法，RGCADP、RGCADP_PS、GCADP 是近似解算法，PSO-GRDKP 是啟發(fā)式算法。所有實驗均在ThinkStation P330 計算機(jī)上進(jìn)行，電腦配置Intel?Core?i7-8700 CPU-3.2 GHz、16 GB DDR4 內(nèi)存、NVIDIA P2200 顯卡，操作系統(tǒng)是Microsoft Windows 10 教育版，算法均使用Python3.6 編碼。

與近似解算法和啟發(fā)式算法相比，BDP 與NEDKP 算法可以獲得最優(yōu)解，但其算法時間性能最差。BDP 與NE-DKP 作為偽多項式時間復(fù)雜度算法，時間復(fù)雜度分別O(nC)、O(nS)，影響算法性能的輸入數(shù)據(jù)規(guī)模分別是C、S。從表2 看出，四類數(shù)據(jù)實例的所有數(shù)據(jù)集有S>C，因此，D{0-1}KP 標(biāo)準(zhǔn)數(shù)據(jù)集上NE-DKP 算法時間性能劣于BDP，即T12>T11。

與BDP、NE-DKP 精確解算法相比，近似解算法和啟發(fā)式算法均大幅度提升了求解時間性能，但各個算法的解誤差率和時間性能提升率各不相同。由表2、表3 看出，RGCADP、RGCADP_PS 的平均解誤差率低于GCADP、PSO-GRDKP 分別達(dá)到4.7 個百分點、0.5 個百分點，GCADP 算法平均解誤差率高于PSO-GRDKP 算法4.2 個百分點。以BDP 算法時間為基線，RGCADP、RGCADP_PS、GCADP、PSO-GRDKP四種算法在D{0-1}KP 標(biāo)準(zhǔn)數(shù)據(jù)集上時間性能提升率分別是71.3%、77.2%、98.2%、75.1%，即GCADP＞RGCADP_PS＞PSO-GRDKP＞RGCADP。GCADP、PSOGRDKP 算法在四類數(shù)據(jù)實例上的時間性能提升率較穩(wěn)定，GCADP 算法在0.979 至0.986 之間變動，PSO-GRDKP 算法在0.728 至0.798 之間變動。RGCADP、RGCADP_PS 算法在不同類型數(shù)據(jù)實例上時間性能提升率差異較大。在IDKP 數(shù)據(jù)實例上，RGCADP、RGCADP_PS 算法時間性能提升率顯著高于GCADP、PSO-GRDKP 算法；在SDKP、UDKP 數(shù)據(jù)實例上，GCADP、PSO-GRDKP 算法較之RGCADP、RGCADP_PS 算法有較為顯著的時間性能優(yōu)勢，但對應(yīng)算法解誤差率表現(xiàn)則相反；在WDKP 數(shù)據(jù)實例上，四類算法時間性能提升率依次有GCADP＞RGCADP_PS＞PSO-GRDKP＞RGCADP，GCADP 算法時間性能最好但解誤差率最高。

RGCADP、RGCADP_PS、GCADP 三類算法均是貪心核動態(tài)規(guī)劃加速算法，當(dāng)C?n時，給定貪心核區(qū)間[s,t] 的算法時間復(fù)雜度是O((t-s+1)CR)，其中，貪心核大小與貪心核上剩余背包容量是影響算法性能的關(guān)鍵因素。因此，貪心核算法優(yōu)化是此類近似算法改進(jìn)的主要途徑。根據(jù)式（10），GCADP 采用的貪心核算法僅是n與b的函數(shù)，雖然算法時間性能提升率達(dá)到98.2%，在不同數(shù)據(jù)類型上算法運行時間偏差不大（如表3 所示）。平均值在三類算法最?。ㄈ绫? 所示），但平均解誤差率達(dá)到4.7%，遠(yuǎn)高于RGCADP、RGCADP_PS算法。RGCADP、RGCADP_PS 所采用的貪心核算法引入相關(guān)系數(shù)ρ區(qū)分?jǐn)?shù)據(jù)類型，考慮了貪心核區(qū)間基于b非對稱分布的特點，與GCADP 算法相比，算法時間性能提升率較低，但有效降低了解誤差率。如表2 所示，在D{0-1}KP 標(biāo)準(zhǔn)數(shù)據(jù)集上兩類算法在多數(shù)數(shù)據(jù)集上可獲得最優(yōu)解。如表2、表3 所示，RGCADP_PS與RGCADP 的求解誤差率較為相近，RGCADP_PS的時間性能提升率高于RGCADP 算法達(dá)到5.9%。其原因是RGCADP_PS 采用分段排序算法對數(shù)據(jù)進(jìn)行預(yù)處理，改進(jìn)了貪心核區(qū)間算法，觀察表4有>，說明RGCADP_PS 有效改善了RGCADP算法的時間復(fù)雜度。圖4 給出了以BDP 算法時間（單位：s）為基線，三種算法在四種數(shù)據(jù)類型數(shù)據(jù)集上時間性能提升率與數(shù)據(jù)規(guī)模的關(guān)系。不難看出，三類算法時間性能提升與數(shù)據(jù)規(guī)模無顯著關(guān)系。

圖4 三類算法時間性能提升率Fig.4 Time performance improvement rate of three algorithms

表2 D{0-1}KP 標(biāo)準(zhǔn)數(shù)據(jù)實例算法實驗結(jié)果Table 2 Algorithm experimental results of D{0-1}KP standard dataset

表3 算法解誤差率與時間提升率Table 3 Solution error rate and time promotion rate of algorithms

表4 貪心核算法背包剩余容量（CR）Table 4 Knapsack residual capacity(CR) of greedy core algorithms

4 結(jié)束語

本文在研究{0-1}KP 核概念基礎(chǔ)上，對文獻(xiàn)[5]的D{0-1}KP 核定義進(jìn)行修正，通過拓展核區(qū)間方式，解決了文獻(xiàn)[5]定義核區(qū)間在有些數(shù)據(jù)實例上出現(xiàn)的不包含不完整項和核區(qū)間邊界值g1>g2情況。為進(jìn)一步縮減D{0-1}KP 修正核區(qū)間規(guī)模，提出一種D{0-1}KP 實例的分段排序策略。改進(jìn)了D{0-1}KP 的貪心核算法，引入項重量和項價值的相關(guān)系數(shù)統(tǒng)計量ρ以反映數(shù)據(jù)類型差異對核區(qū)間算法的影響。應(yīng)用分治算法設(shè)計模式，構(gòu)造了RGCADP、RGCADP_PS 兩種貪心核動態(tài)規(guī)劃加速求解算法。D{0-1}KP 四種類型數(shù)據(jù)實例上運行結(jié)果表明：

（1）與精確解算法BDP相比，RGCADP、RGCADP_PS 算法平均求解時間提升率為71.3%、77.2%。

（2）RGCADP、RGCADP_PS 算法平均解誤差率較之啟發(fā)式算法PSO-GRDKP 低0.5 個百分點，平均求解時間提升率接近PSO-GRDKP 算法。

（3）與GCADP 算法相比，RGCADP、RGCADP_PS 算法時間性能提升率較低，但平均解誤差率較之高4.7 個百分點。

（4）RGCADP_PS 與RGCADP 的求解誤差率較為相近，但RGCADP_PS 的時間性能提升率較RGCADP 算法高5.9%。

以上結(jié)果表明，基于核區(qū)間修正定義和分段排序策略的貪心核算法較顯著改善了D{0-1}KP 貪心核加速動態(tài)規(guī)劃算法性能。為進(jìn)一步驗證本文所提出D{0-1}KP 貪心核定義采用不同核加速算法的性能表現(xiàn)，接下來考慮采用粒子群算法計算貪心核解向量，設(shè)計RGCAPSO、RGCAPSO_PS 兩種算法，并與本文提出算法進(jìn)行性能對比研究。