计算机应用

作者：史文旭, 杨洋, 鲍胜利

单位：1. 中国科学院大学, 北京 100049;2. 中国科学院 成都计算机应用研究所, 成都 610041;3. 西华师范大学 数学与信息学院, 四川 南充 637009

关键词：折扣{0-1}背包问题,贪心核加速动态规划算法,新型贪心修复优化算法,核算法,基础动态规划

基金：四川省科技厅重点研发项目（2018SZ0040）；四川省大学生创新创业训练计划支持项目（201810638085）。

针对现有动态规划算法求解折扣{0-1}背包问题（D{0-1}KP）缓慢的问题，基于动态规划思想并结合新型贪心修复优化算法（NGROA）与核算法，通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划（GCADP）算法。首先利用NGROA对问题进行贪心求解，得到非完整项；然后通过计算得到模糊核区间的半径和模糊核区间范围；最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划（BDP）算法求解。实验结果表明：GCADP算法适用于求解D{0-1}KP，且在求解速度上相比BDP算法平均提升了76.24%，相比FirEGA算法平均提升了75.07%。

来源：2019年第7期

《计算机应用》期刊编辑部

查看计算机应用杂志2019年第7期