王茂萍 潘大志 冯世强

摘 要：针对背包容量折扣系数在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的進化算法已有很多……