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

Greedy core acceleration dynamic programming algorithm for solving discounted {0-1} knapsack problem

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

As the existing dynamic programming algorithm cannot quickly solve Discounted{0-1}Knapsack Problem(D{0-1}KP),based on the idea of dynamic programming and combined with New Greedy Repair Optimization Algorithm(NGROA)and core algorithm,a Greedy Core Acceleration Dynamic Programming(GCADP)algorithm was proposed with the acceleration of the problem solving by reducing the problem scale.Firstly,the incomplete item was obtained based on the greedy solution of the problem by NGROA.Then,the radius and range of fuzzy core interval were found by calculation.Finally,Basic Dynamic Programming(BDP)algorithm was used to solve the items in the fuzzy core interval and the items in the same item set.The experimental results show that GCADP algorithm is suitable for solving D{0-1}KP.Meanwhile,the average solution speed of GCADP improves by 76.24%and 75.07%respectively compared with that of BDP algorithm and FirEGA(First Elitist reservation strategy Genetic Algorithm).