贪心核加速动态规划算法求解折扣{0-1}背包问题

论文摘要

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

论文目录

• 0 引言
• 1 D{0- 1}KP模型
• 2 改进核算法
•   2.1 精确核算法
•   2.2 近似核算法
•   2.3 贪心策略
•   2.4 FCI求解算法
• 3 GCADP算法
•   3.1 DP求解{0- 1}KP
•   3.2 BDP求解D{0- 1}KP
•   3.3 GCADP求解D{0- 1}KP
• 4 实例计算与结果对比
•   4.1 四类实例
•   4.2 求解结果及比对
• 5 结语

文章来源

类型: 期刊论文

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

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

来源: 计算机应用 2019年07期

年度: 2019

分类: 信息科技,基础科学

专业: 数学

单位: 中国科学院大学,中国科学院成都计算机应用研究所,西华师范大学数学与信息学院

基金: 四川省科技厅重点研发项目(2018SZ0040),四川省大学生创新创业训练计划支持项目(201810638085)~~

分类号: O221.3

页码: 1912-1917

总页数: 6

文件大小: 191K

下载量: 397