计算机科学与探索

作者：代祖华, 刘园园, 狄世龙, 樊琦

单位：西北师范大学 计算机科学与工程学院，兰州 730070

关键词：折扣{0-1}背包问题,核区间定义修正,贪心核算法,分段排序,贪心核动态规划加速算法

折扣{0-1}背包问题（D{0-1}KP）的贪心核算法是一种近似解算法，常通过估算核区间划分子问题，采用分治算法设计求解算法，算法性能与核区间估计准确性密切相关，核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上，提出D{0-1}KP核区间的修正定义，构建分段排序策略以缩减核区间规模，改进了D{0-1}KP贪心核算法，设计了修复贪心核动态规划加速算法（RGCADP）、分段排序贪心核动态规划加速算法（RGCADP_PS）。两个算法在D{0-1}KP标准数据集上的实验结果表明：与基本动态规划算法（BDP）相比，RGCADP、RGCADP_PS算法平均求解时间提升率为71.3%、77.2%；RGCADP、RGCADP_PS算法平均解误差率低于粒子群贪心修复算法（PSO-GRDKP）0.5个百分点，低于贪心核加速动态规划（GCADP）算法4.7个百分点；RGCADP_PS时间性能提升率高于RGCADP算法5.9%。

来源：2023年第3期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2023年第3期