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

摘要

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