贪心核加速动态规划算法精确求解适用范围

王茂萍 潘大志 冯世强

摘 要：针对背包容量折扣系数在0.8～0.9时，贪心核加速动态规划算法（GCADP）无法求得逆向强相关折扣{0-1}背包问题实例（IDKP）精确解的问题，为求得D{0-1}KP实例的精确解，在对IDKP实例参数进行分析的基础上，给出GCADP算法能精确求解D{0-1}KP实例的限定条件：任意项集的价值系数满足价值最小项大于价值次大项的0.99倍。将该条件应用到4类D{0-1}KP实例的参数设置中，生成新的大规模D{0-1}KP实例。对4类D{0-1}KP实例运用GCADP和动态规划（DP）进行计算，计算结果表明，新的4类D{0-1}KP实例均得到精确解，并且GCADP随着数据规模的变大，求解时长增长平缓。

关键词：折扣{0-1}背包问题;贪心核加速动态规划算法;动态规划;价值密度;贪心策略

DOI：10. 11907/rjdk. 192600 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）008-0054-06

Abstract：The greedy core acceleration dynamic programming algorithm（GCADP） cant find the exact solution of the instance when solving the inverse strongly correlated instances of D{0-1}KP（IDKP） with the knapsack capacity discounted coefficient of 0.8-0.9. In order to obtain the exact solution of the D{0-1}KP instance， based on the analysis of the IDKP instance parameters， the GCADP algorithm can accurately solve the D{0-1}KP instance with limited condition that the value coefficient of any item set satisfies the smallest value item and is greater than 0.99 times the second largest value item. This condition is applied to the parameter settings of the four types of D{0-1}KP instances to create a new large scale four-class D{0-1}KP instance. The four types of D{0-1}KP instances use GCADP and dynamic programming（DP） calculations. Instances calculation results show that the new four types of D{0-1}KP instances are all accurately solved， and the data size increases， the solve time of GCADP grows slowly.

Key Words：discount {0-1} knapsack problem; greedy core acceleration dynamic programming algorithm; dynamic programming; value density; greedy strategy

0 引言

折扣{0-1}背包问题（Discounted{0-1} Knapsack Problem， D{0-1}KP）是基于经典{0-1}背包问题（{0-1} Knapsack Problem， {0-1}KP）提出的一种拓展形式，也是典型的组合优化问题[1-2]。在实际生活中，某一商场有大量商品A和商品B，为避免出现商品滞销，商场推出商业打折活动，将商品A和商品B以一定折扣系数捆绑在一起进行销售，由其刻画的数学模型便是D{0-1}KP，其折扣捆绑销售的特点可实现商业价值最大化，因此该模型在生活中得到了广泛应用[3]。

多个目标的D{0-1}KP问题是由Guldan[3-5]提出的，并给出了它的启发式和确定性算法，通过动态规划达到求解目的。Rong等将传统背包问题中的核问题与D{0-1}KP相结合，求解基于核问题的动态规划改进方法，但确定性算法的求解时间较长，缺乏实用性。目前，求解D{0-1}KP的進化算法已有很多可参考的成果，如冯艳红等[6]运用差分进化帝王蝶优化算法求解D{0-1}KP，均得到近似解，且近似比为1;刘雪静等[7]提出自适应细菌觅食算法求解D{0-1}KP，均获得最优解;贺毅朝等[8]利用遗传算法求解D{0-1}KP的第二数学模型和第三数学模型;杨洋等[9]在动态规划思想基础上，结合核算法和新型贪心修复优化算法（New Greedy Repaired Optimization Algorithm， NGROA），通过缩小D{0-1}KP规模实现加速求解问题的目的，并提出贪心核加速动态规划算法（Greedy Core Acceleration Dynamic Programming Algorithm， GCADP）。但从文献[9]的实例计算与结果对比中发现，仅有逆向强相关实例（Inverse Strongly Correlated Instances of D{0-1}KP， IDKP）通过GCADP求解可得到精确解，其它3类实例均有误差率。因此，本文探讨如何确定GCADP的精确求解适用范围。

1 D{0-1}KP定义及数学模型

定义1[10-16]：给定[n]个均含有3个项（或物品）的项集，项集[i]（[0in-1]）中含有的3个项分别记为[3i]、[3i+1]、[3i+2]，其中前两项[3i]、[3i+1]具有的价值系数分别为[p3i]和[p3i+1]，重量系数分别为[w3i]和[w3i+1]。前两项合并在一起构成第3项[3i+2]，其具有的价值系数为[p3i+2=p3i+p3i+1]，折扣重量系数为[w3i+2]，满足[w3i+2

显然，运用DP求解D{0-1}KP是一个填充零矩阵[V]的过程，[V]中元素均为当前物品组合的最大值，所以該矩阵最后一位元素为该问题的精确解。当物品规模较大时，利用DP求解D{0-1}KP耗时较长，因此实用性较差，可考虑缩小问题规模，从而达到快速求解的目的。

2.3 GCADP求解D{0-1}KP

GCADP首先通过模糊核区间（Fuzzy Core Interval， FCI）算法确定模糊核区间的上界和下界，再处理模糊核区间内的数据，使其数据所在项集均不被选中，最后对模糊核区间内的物品运用动态规划算法进行求解，从而得到最终解。

FCI算法中的贪心策略选择与传统方法不同，传统GROA是选择价值密度最大的，而NGROA是选择价值最大的。通过核算法的贪心选择确定模糊核区间的核中心和核半径，经过数据处理后，按价值密度从大到小进行排列，从初始物品到模糊核区间下界之前的物品均被选中。因此，只需确认模糊核区间内的物品选择情况即可，从而缩小问题规模，再利用DP对模糊核区间内的物品进行求解，实现缩短整体时长的目的。通过实例计算结果进行对比，发现GCADP对IDKP实例能得到精确解，其它3类实例可得到较好的近似解。

3 IDKP背包容量

传统实例背包容量为[C=αi=0n-1w3i+2，] [α]为[0.45，0.75]上的一个随机数。GCADP对传统IDKP均能得到精确解，若将IDKP背包容量中的[α]扩大为[0.8，0.95]上的随机数，在GCADP的求解模糊核区间FCI算法中进行贪心求解时，随着背包容量的扩大，被选中的项集数目也随之增多。此时，未在GCADP精确求解适用范围内的项集被选入背包内，因此GACDP不再对IDKP作精确求解。本文选取折扣系数[α]分别为0.8、0.85、0.9和0.95，运用GCADP和DP对IDKP的求解结果与求解时间如表1所示。

本文使用的工作站为HP Z8 G4（Z3Z16AV-SC001），操作系统为Windows 10 专业版，硬件配置为Intel（R） Xeon（R） Silver 4114 CPU @ 2.20GHz 2.19GHz，32.00GB ，利用MATLAB18a对问题进行绘图求解。记DP的结果为[Opt1]，计算时长为[T1];GCADP的结果为[Opt2]，计算时长为[T2]（[T1，T2]单位为秒）。设置误差率（Error Rate， ER）计算方式为：[ER=1-Opt2Opt1]。

由表1可知，当更改背包容量[C]后，仅有IDKP1均达到精确解，IDKP2～IDKP10随着折扣系数的增大，误差也随之增大，此时GCADP对ID KP不再达到精确解。说明IDKP的原始数据特性满足GCADP精确求解适用范围的部分，当背包容量[C]扩大时，不再精确求解。因此，考虑IDKP的参数特性，得到GCADP的精确求解适用范围。

4 IDKP参数设置

在文献[9]中，GCADP仅对4类D{0-1}KP原始实例中的IDKP有正确的贪心选择策略，使其达到精确解。但通过扩大折扣系数将背包容量扩大后，IDKP实例也达不到精确解。因此，本节通过探究IDKP与其它3类实例参数设置之间的差异性，发现IDKP的参数特性，从而找到GCADP精确求解的适用范围。

4.1 IDKP参数特性

基于参考文献[8]中4类D{0-1}KP实例的参数设置，给出IDKP实例的参数设置：[p3i∈R2，1000，][p3i+1∈][R2，1000，][p3i

因此，当实例参数设置均满足[e3i

5 四类D{0-1}KP实例计算与结果分析

5.1 四类实例

通过以上证明发现，[e3i

5.2 求解结果与对比

通过GCADP与DP对4类实例进行求解，得到表2、表3的结果，为了更清晰地看出GCADP与DP的求解速率，将表2、表3的时长绘制为图1。

从表2、表3中可以看出：在更改参数设置后的UDKP等4类实例计算中，将背包容量的折扣系数[α]扩大为0.8、0.85、0.9、0.95，GCADP与DP的求解结果相同。由于电脑运行内存有限，当UDKP5、WDKP5、SDKP5和IDKP5的数据规模与背包容量较大时，DP不能构造出零矩阵，因而不能对其进行动态规划求解。因此，在表2、表3中针对该部分实例的运算结果用“—”表示，同时对该部分实例采用CPLEX运算，其结果与GCADP的求解结果一致，说明GCADP对4类实例均能实现精确求解。因此，该限定条件：第[i]个项集的价值系数满足[99100p3i+1

6 结语

本文通过分析IDKP这类实例的通用参数设置，发现当第[i]个项集的价值系数满足[99100p3i+1

参考文献：

[1] GUDER J. Discounted knapsack problems for pairs of items [D].  Erlangen： Friedrich-Alexander-Universit t Erlangen-Nürnberg，2005.

[2] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Erlangen：Friedrich-Alexander-Universit t Erlangen-Nürnberg， 2007.

[3] BAO L，CAO J，LI J，et al.Boosted near-miss under-sampling on SVM ensembles for concept detection in large-scale imbalanced datasets[J]. Neurocomputing，2016，172：198-206.

[4] LOYOLA-GONZALEZ O，MARTINEZ-TRINIDAD J F，CARRASCO-OCHOA J A，et al.Effect of class imbalance on qualitymeasures for contrast patterns：an experimental study[J]. Information Sciences，2016（374）：179-192.

[5] GONG J，KIM H.RHSBoost：improving classification performance in imbalance data[J]. Computational Statistics &Data Analysis，2017（111）：1-13.

[6] 冯艳红，杨娟，贺毅朝，等. 差分进化帝王蝶优化算法求解折扣{0-1}背包问题[J]. 电子学报，2018，46（6）：1343-1350.

[7] 刘雪静，贺毅朝，吴聪聪，等. 基于细菌觅食算法求解折扣{0-1}背包问题的研究[J]. 计算机工程与应用，2018，54（2）：155-162.

[8] 贺毅朝，王熙照，李文斌，等.  基于遗传算法求解折扣{0-1}背包问题的研究[J]. 计算机学报， 2016， 39（12）： 2614-2630.

[9] 史文旭，杨洋，鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用，2019（7）：1912-1917.

[10] 杨洋，潘大志，刘益，等. 折扣{0-1}背包问题的简化新模型及遗传算法求解[J]. 计算机应用， 2019， 39（3）：656-662.

[11] 杨洋，潘大志，贺毅朝. 改进修复策略遗传算法求解折扣{0-1}背包问题[J].  计算机工程与应用， 2018， 54（21）： 37-42.

[12] 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 & Applications， 2018（30）： 3019-3016.

[13] 杨洋，潘大志，贺毅朝.  核加速遗传算法求解折扣{0-1}背包问题[J]. 西华师范大学学报（自然科学版），2018，39（2）：165-172.

[14] 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.

[15] YICHAO H， XINLU Z， JIANMIN S. Design method of the iterative algorithm based on dynamic programming [J].  Mathematics In Practice and understanding， 2016， 46（6）： 173-180.

[16] KELLERER H， PFERSCHY U， PISINGER D. Knapsack problems[M].  Springer Berlin Heidelberg， 2004.

[17] BELLMAN R. Dynamic programming[J]. Science，1966，153： 34-37.

[18] 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.

[19] KATHRIN K，WIECEK M M. Dynamic programming approaches to the multiple criteria knapsack problem[J]. Naval Research Logistics， 2015， 47（1）：57-76.

[20] 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.

（责任编辑：黄 健）