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

Greedy Core Acceleration Dynamic Programming Algorithm to Accurately Solving Range

作　　者：王茂萍 潘大志[1,2] 冯世强[1] 张琴 WANG Mao-ping;PAN Da-zhi;FENG Shi-qiang;ZHANG Qin(College of Mathematics and Information,China West Normal University,Nanchong 637009,China;Institute of Computing Method and Application Software,China West Normal University,Nanchong 637009,China)

机构地区：[1]西华师范大学数学与信息学院,四川南充637009 [2]西华师范大学计算方法与应用研究所,四川南充637009

出　　处：《软件导刊》2020年第8期54-59,共6页Software Guide

基　　金：国家自然科学基金项目(11871059);四川省教育厅自然科学基金项目(18ZA0469);西华师范大学校级科研团队项目(CXTD2015-4)。

摘　　要：针对背包容量折扣系数在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随着数据规模的变大,求解时长增长平缓。The greedy core acceleration dynamic programming algorithm(GCADP)can’t 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 algo⁃rithm 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 instanc⁃es are all accurately solved,and the data size increases,the solve time of GCADP grows slowly.

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]