0-1背包问题又称为子集合问题，属于经典的NP难问题．问题可以简单表述为：在n类有确定质量与价值的物品中选择若干个物体放入容量有限的一个背包中，使得背包装入物品的总价值最大．在背包问题中，若每个物品可以被选择多次，且装入时不可拆分，则称为完全0-1背包问题．该问题常见于任务调度、投资选择、密匙生成和材料切割等场景，在理论研究与实际应用方面有着重要价值[1]．求解0-1背包问题的算法可分为确定性算法与群智能算法两大类．穷举法、分支界定法、回溯法和动态规划法等算法会枚举所有可行解，属于经典的确定性求解算法，这种算法能够求出精确解，但时间复杂度大多呈指数爆炸，难以求解大规模的问题．而群智能算法一般可以在多项式时间内近似地求解大规模的0-1背包问题．随着科学技术的发展和新型算法策略的不断涌现，0-1背包问题的求解算法也由传统方法逐渐发展出众多的新型智能算法，如量子狼群算法、萤火虫算法、烟花算法、混合蝙蝠算法、果蝇优化算法等[2-7]．如离散正余弦算法[4]使用非线性指数递减函数来更新个体步长，避免搜索的盲目性；混合蝙蝠算法[6]是在基本蝙蝠算法的基础上进行改进等，虽然在一定程度上能够提高搜索能力和求解速度，但并不能保证找到问题的最优解，其算法的高效性是以牺牲算法的最优性为代价的．此外，也有不少算法研究工作从传统背包问题出发，给出了基于不同物品属性的求解算法[8]，或者将算法优化目标从单一价值扩展双目标[9]乃至多目标[10]从而将背包问题推广到不同领域．但纵观已有的算法，均无法同时满足最优性和高效性，本研究从传统的动态规划算法出发，提出了基于贪心回溯思想的局部动态规划算法，在保证最优的前提下，大大提升了原算法的性能．由于动态规划(dynamic programming，DP)方法并不关注物品的单位平均价值，而对背包容量进行遍历，因此可能出现大量冗余计算．考虑最大单位平均价值的特殊性，基于贪心思想进行最大单位平均价值成分的选取从而避免了冗余计算，然后利用动态规划进行回溯，对贪心的结果进行小范围的修正，以确保算法的正确性．对于一般的价值数据，本研究提出的基于贪心回溯思想的局部动态规划算法(local dynamic programming based on greedy and backtracking，LDPGB)能够大大减小须要动态规划求解的范围，从而显著提升求解速度．1 基于贪心回溯的局部动态规划算法1.1　0-1背包问题概述经典的0-1背包问题可以简单描述为：给定n种物品集合S={1，2，…，n}和一个背包容量为C的背包．每一种物品i都有它的质量wi和价值vi (i=1，2，…，n)．求最优装包方案(x1，x2，…，xn)，xi∈C (xi为背包中装载物品i的数量)，使得背包的总质量W不超过C的同时获得的价值V达到最大．当选择物品装入背包时，物品只有整体装入或不装入两种状态．问题可以表述为：V=max∑i  =  1nvixi;s.t.∑i  =  1nwixi≤C,xi∈{0,1}. (1)式(1)中，若xi的取值范围由0或1拓展为非负整数，则问题转变为完全0-1背包问题．相应地，问题可以表述为：V=max∑i  =  1nvixi;s.t.∑i  =  1nwixi≤C,xi∈{0,1,⋯}. (2)下面以表1中数据为例进行说明．10.13245/j.hust.240201.T001表1物品参数表wi12345678910vi1589101717202431.2　完全0-1背包问题的求解思路首先求解各个物品所对应的单位平均价值pi=vi/wi，(3)然后比较各个物品的单位平均价值，得到最大的单位平均价值pα=max1≤i≤n{pi}, (4)以及次大单位平均价值pβ=max1≤i≤n,pi  ≠  pα{pi}．(5)记pα和pβ的对应物品的质量、价值、序号分别为wα，vα，α和wβ，vβ，β．定理1 当容量C恰好是wα的整数倍时，直接用质量为wα的物品装满背包即可得到最大价值．证明 针对任意的装包方案X={x1,x2,⋯，xn}，应满足如下限界条件：xi∈N    (xi≤C/wi);∑i  =  1nxiwi≤C. (6)定义对于装包方案X，对应的价值和为sX=∑i  =  1nvixi．(7)当C可以被wα整除时，若全部用wα对应的物品装满背包，记价值和为sα=vαC/wα=pαC．(8)根据(4)和(7)，可以证明sX=∑i  =  1n(piwixi)≤∑i=1n(pαwixi)=pα∑i=1nwixi≤pαC=sα.从而得到结论：对于任意装包方案X，只要wα能够整除背包容量C，则X对应的装包物品价值总和小于sα恒成立，即∀wα,X,C,wα|C⇒sXsα．(9)但在一般情况下，即当C不能够被wα整除时，无法保证只用wα对应的物品装入背包得到的总价值最大．例如，当C=27时，可以得到最优装包方案X1=1,0,0,0,0,1,0,0,0,2及其总价值sX1=78．即背包中物品质量为{1，6，10，10}．而只用质量为wα填装背包的装包方案X2总价值sX2=77，其中X2={0,0,0,0,0,0,1,0,0,2}．(10)显然sX1sX2，发生这种情况的原因是：在p1中将X2的容量7拆解成了容量1+6，然后分别填装，因此可知用平均价值最大的物品贪心地装入背包不一定得到最优解，须要用动态规划进行部分回溯来保证算法的正确性．但是，注意到如果Cn，在动态规划得到的方案X1中也存在两个wα(按照表1值为10)，不难想到当剩余容量大于wα时，装包方案中包含的wα对应物品越多越好．1.3　最大价值成分定理本研究采用以下的子问题划分方式：任何一种装包方案都可以拆分为两个部分，即只用第α个物体和不用第α个物体装包．也就是对于一个方案X=(x1,x2,⋯,xα,…,xn)，可将其拆分为X1和X2，使其满足：X=X1+X2;X1⋅X2=0. (11)假设X1，X2的形式为：X1={x1,x2,⋯,xα-1,0,xα+1,⋯,xn};X2={0,0,⋯,xα,⋯,0}.同样地，可以将背包分割为两部分：一部分的容量为xαwα，用于X2方案；另一部分容量为C-xαwα，用于X1方案．而由式(9)可知，X2方案即为其对应部分背包的最优解．根据最优子结构性，X1方案也应当为对应部分背包的最优解．于是，要求解最优方案，只需求解该分割点．定理2(最大价值成分定理)　设i为某一分割点，定义价值成分Ωi=iwα/C，剩余容量m=C mod wα则∀Ωi≤Ωt,si≤st，(12)其中t=Cwα-pβm-r[m](pα-pβ)wα-1，(13)式中r[m]为总质量为m的物品可以得到的最大价值．最大价值成分定理表明：当寻找最大价值的装包方案时，只须关注分割点限界t及t之后的情况，无须再考虑t之前的分割情况．证明 由0≤i≤C/wα可知，在这种划分方式下，装包方案只有C/wα+1种情况，只要计算这C/wα+1种情况中总收益的最大值即可．最大收益可表示为M=max0≤i≤C/wα{pαiwα+r[C-iwα]}．(14)当i≤t时，即i≤Cwa-pβm-r[m](pα-pβ)wα-1成立时，移项可得Cwα-i≥pβm-r[m](pα-pβ)wα+1，从而有Cwα-i≥pβm-r[m](pα-pβ)wα+1，(15)进而得到pβ(C-iwα)≤(C-(i+1)wα)pα+r[m]-pβm+pβwα. (16)因为在对X1进行动态规划时不用α号物品装包，所以X1的所有装包方式的平均价值必然小于等于pβ，则rnew[C-iwα]≤pβ(C-iwα)．(17)用rnew[∙]表示将第α号物品去掉后按照传统动态规划算法求得的最大值，因此可做以下推导．第i种分割方法的价值为si=pαiwα+rnew[C-iwα]．(18)在动态规划部分，最大单位平均价值为pβ，所以这一部分的价值一定小于等于全部按照pβ售出的价值，从而可以放缩为si≤pαiwα+pβ(C-iwα)．(19)又由式(16)可以将式(19)继续放缩，即si≤pαiwα+(C-(i+1)wα)pα+r[m]-pβ(m-wα)=pα(C-m)+r[m]-(wα-m)(pα-pβ)≤pα(C-m)+r[m],进而得到si≤pα(C-m)+r[m]．(20)也就是说，当i≤t时的价值小于i=C/wα时的价值，则最优分割点i必然大于等于t．值得注意的是，当pα和pb大小接近时，t为负数，在这种特殊情况下，算法退化为传统动态规划算法．2 局部动态规划算法本节在最大价值成分定理的支持下，提出局部动态规划算法LDPGB．算法的思路是采用贪心缩小问题规模，再进行回溯保证结果正确性的动态规划算法．2.1　算法描述首先，为了保证最终的价值最大，应尽量多地装入α号物品，因此运用贪心思想，先填装C/wα个α号物品，再对剩余容量m=C mod wα进行回溯，每次回溯使剩余容量增加wα，直至找到某一个分割点，使得价值最大．由式(14)可知，此时背包被分为两部分，一部分全部装入α号物品，而另一部分的装包方案可以使用动态规划算法在去除α号物品的剩余可选物品中进行求解．由最大价值成分定理可知，回溯次数上界km可提前计算，km=Cwα-t=pβm-r[m](pα-pβ)lα+1．(21)于是须要动态规划的容量范围也可以事先确定，因此在事先计算好回溯上界及须要用动态规划求解的一定容量范围内的最大价值后，可以求出总体的最大价值．LDPGB算法首先进行小规模的动态规划求出r[wα]，之后根据式(21)求出分割点的限界t，对km大小的背包使用动态规划，最后计算每个分割点的对应总价值并选出其中最大值．算法伪码如算法1所示．算法1　LDPGB算法输入　value,weight,n,C输出　maximum profit Mlet r[wα+1] be a new arrayuse DP to figure out the array rvalue[α]=0km=pβm-r[m](pα-pβ)wα+1let rnew[kmwα+m+1] be a new arrayuse DP to figure out the array rnewM=0For i=0 to km doM=max(ans,pαwα(C-i)+rnew[m+iwα])EndReturn M2.2　算法复杂度分析本算法中使用了两个动态规划数组，第一个动态规划数组r的大小正比于wα，其空间复杂度为O(wα)；第二个动态规划数组rnew的空间复杂度为O(kmwα)．对于时间复杂度，初始化时找到wα和wβ只须遍历一遍w数组，故而时间复杂度为O(n)．LDPGB算法第一、二步动态规划的时间复杂度分别为O(nwα)和O(nkmwα)．最后求M的循环的时间复杂度为O(km)．值得注意的是，当pα与pβ非常接近时，km非常大，这时本算法相当于用动态规划对问题进行求解，即算法退化为传统动态规划算法．3 实验结果与分析目前，除了动态规划(DP)算法之外，并没有能够很好解决完全背包问题的完备精确算法，所以接下来均以DP作为比较对象测试LDPGB的性能．LDPGB算法的正确性可以根据表2和3中两算法的运行结果总是相同得到验证，因此实验分析时着重讨论LDPGB算法求解时间(τ)的变化规律．10.13245/j.hust.240201.T002表2DP与LDPGB在常规数据下的求解时间与结果变化情况nC/103τ/sMDPLDPGBDPLDPGB1 00020.0020.0018118111 000200.0280.00118 00018 0001 0001000.1200.00140 55640 5561 0002000.2580.001133 333133 3331 0005000.5990.001450 000450 0001 0001 0001.1510.001453 333453 3333.1　LDPGB与DP在常规数据下的求解性能对比本研究主要考虑在常规数据下，LDPGB与DP的效率对比．对正常规模的设定如下：n=1 000，pi的差异在0.01~1之间，C的规模从2 000到20 000变化，得到的结果如图1(a)所示，可以看出：DP的时间随C的增加呈线性增长趋势，而LDPGB算法对C的增加不敏感；同时，DP的时间随C的增加呈线性增长趋势，而LDPGB对C的增加不敏感．表2为部分特定规模C对应的DP和LDPGB的求解时间与结果的具体数据．10.13245/j.hust.240201.F001图1LDPGB和DP的求解时间与背包容量关系曲线采用增加求解规模的方式得到图1(b)．当求解规模较大时，能够明显得到DP和LDPGB对应的曲线都平滑了许多，但是曲线的变化趋势依旧分别是线性增加和接近常数．另外，从图1可以看出：一般情况下，LDPGB在求解此类问题时的时间性能是非常优越的，原因在于LDPGB的时间复杂度只依赖于数据成分，而不依赖于数据规模，这点从表2中各行LDPGB求解的时间几乎相等可以进一步得到验证．由3.2节可知：LDPGB求解的时间花费主要取决于限界t的大小；t的计算如式(13)所示，显然，pα-pβ越小，LDPGB回溯路径就越长．接下来，主要通过控制pα-pβ的大小来控制变量，进行多组实验．部分典型数据实例如表2所示，可以看到LDPGB表现出的时间性能非常优越且稳定．图1中，DP曲线的变化趋势验证了在第1，2节分析的DP的时间复杂度TDP(n,C)=O(nC)，在n一定的情况下TDP∝C；而在LDPGB中，时间耗费完全取决于回溯的过程，回溯完成后问题也就求解完成，在n与w，v数组都给定的情况下，LDPGB曲线近似为一条直线，也验证了这一点．3.2　LDPGB与DP在非常规数据下求解性能对比本节尝试寻找LDPGB比传统DP优越的边界条件，因此有意缩小最大单位平均价值和次大单位平均价值，意在增加LDPGB的回溯路径长度以提高LDPGB的求解时间，然后对于更大跨度的n进行随机生成与求解．具体的操作是控制pα-pβ由原来的1×10-1量级进一步缩小到1×10-3乃至1×10-4量级，得到的结果如图2(a)所示，与4.1节同理，为了增加实验结果的准确性与可信度，增加求解规模可以得到图2(b)，具体的数据结果如表3所示．10.13245/j.hust.240201.F002图2LDPGB和DP求解时间与n的关系曲线10.13245/j.hust.240201.T003表3DP与LDPGB在非常规数据下的求解时间与结果变化情况nC/103τ/sMDPLDPGBDPLDPGB1 000100.0120.0010.040 50.040 53 000100.0360.0070.032 60.032 68 000100.0650.0430.030 00.030 01 0001000.1280.0011.022 21.022 25 0001000.7160.0160.588 90.588 910 0001001.1340.0610.855 60.855 6从图2(a)中可以看出：对于pα-pβ的量级缩小，LDPGB的求解性能仍然远优于DP．接下来，进一步增加量级的缩小规模寻找LDPGB的最优执行范围边界．同时由图2和表3可知：随着C的增长，DP求解时间呈线性增长趋势而LDPGB基本不变，两条曲线在图2(a)中比在图2(b)中更接近；因此，为了得到最佳适用范围的边界(须探索DP和LDPGB对应的曲线何时有相交的趋势)，4.3节在图2(a)的小求解规模上进行操作．值得一提的是，在图2中，LDPGB算法的时间并不是像图1中一样一成不变的，因为从第3.2节的算法复杂度分析可知，LDPGB有一个时间复杂度为O(nwα)的求解t的过程和时间复杂度为O(n)的寻找wα和wβ的过程，所以当总体时间在wα一定时，O(nwα+n)正比于n．图1中n是保持不变的，而图2中n是线性增加的，因此LDPGB在前者中时间保持近乎恒定，在后者中线性增加．3.3　LDPGB与DP在极端数据下的求解性能对比在图2(a)中，当pα-pβ减少3个量级时，LDPGB曲线并不能明显地逼近DP，因此为了寻求LDPGB最佳适用范围的边界，直接将pα-pβ的量级在之前的基础上进一步缩小9个量级，然后在同样的变量控制条件下分别测试LDPGB和DP的求解性能，得到的结果如图3所示．10.13245/j.hust.240201.F003图3LDPGB和DP的求解时间与n的关系曲线从图3中得到，在极端数据下随n的增长，LDPGB曲线逐渐逼近DP曲线．由t的定义可知，当pα-pβ非常小时，km非常大，而本算法回溯时动态规划的规模是O(kmwα)，此时LDPGB趋近于DP；并且由于LDPGB的预处理等步骤须要一定运行时间，因此当最大单位平均价值与次大单位平均价值的差距非常小时，LDPGB的求解时间可能超过DP．而这也表明，当实际应用LDPGB求解问题时，可以加入一个判定：当pα-pβ成分的量级超出最优执行边界时，LDPGB退化为DP算法，从而保证在任何情况下，LDPGB的时间性能总是不劣于并且绝大多数时候是优于DP算法的．表4给出两组在人为构造的极端特殊用例下LDPGB和DP的性能对比，此时的LDPGB求解时间比DP长，不过仍相差不大．10.13245/j.hust.240201.T004表4DP与LDPGB在极端数据下求解时间对比情况n/103C/103τ/sM/10-7DPLDPGBDPLDPGB1100.0120.0014.064.073100.0380.0086.116.116100.0590.0269.119.119100.0830.0647.007.0010100.0950.1347.227.224 结语本研究根据平均价值提出了一种基于贪心回溯的局部动态规划算法，显著缩减了经典动态规划算法针对常见的完全背包问题的计算复杂度，在时间复杂度及空间复杂度方面均有明显的优势．同时，“局部贪心带回溯”的思想也为须要保证精确性的算法优化问题提供了新思路，即并不是所有的优化方法都像群智能等优化算法一样须要以牺牲结果精确性为代价来提升算法的执行效率．当然，关于LDPGB算法的其他问题还有待进一步研究，比如当求解规模C稍大于n时，是否可以给出更高效的判断策略，判断此时是否不适合直接使用LDPGB算法，而非当不适合时，LDPGB算法因回溯路径过长而被动退化为DP算法等．