贪心核加速动态规划算法求解折扣{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。请明确。回复：不需要修改，Vv（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）步表示该项集是否选择第一个物品（质量和价值均最小），第13）～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不仅在求解速度上快速提高，且问题的求解精度也更优秀。总体而言，因为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.