科研之友
微信
新浪微博
Facebook
分享链接
摘要
折扣{0-1}背包问题（Discounted{0-1}Knapsack Problem， D{0-1}KP）的贪心核算法是一种近似解算法，常通过估算核区间划分子问题，采用分治算法设计求解算法，算法性能与核区间估计准确性密切相关，核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上，提出D{0-1}KP核区间的修正定义，构建分段排序策略以缩减核区间规模，改进了D{0-1}KP贪心核算法，设计了修复贪心核动态规划加速算法（repaired greedy core acceleration dynamic programming algorithm， RGCADP）、分段排序贪心核动态规划加速算法（repaired greedy core acceleration dynamic programming algorithm via piecewise sorting，RGCADP＿PS）。两个算法在D{0-1}KP标准数据集上的实验结果表明：与基本动态规划算法（Basic Dynamic Programming， BDP）相比，RGCADP、RGCADP＿PS算法平均求解时间提升率为71.3%、77.2%；RGCADP、RGCADP＿PS算法平均解误差率低于粒子群贪心修复算法（particle swarm optimization based greedy repair algorithm for D{0-1}KP，PSO-GRDKP）0.5%，低于贪心核加速动态规划（greedy core acceleration dynamic programming algorithm，GCADP）算法4.7%；RGCADP＿PS时间性能提升率高于RGCADP算法5.9%。
- 单位
