折扣{0-1}背包问题之分段排序贪心核算法研究

折扣{0-1}背包问题(D{0-1}KP)的贪心核算法是一种近似解算法,常通过估算核区间划分子问题,采用分治算法设计求解算法,算法性能与核区间估计准确性密切相关,核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上,提出D{0-1}KP核区间的修正定义,构建分段排序策略以缩减核区间规模,改进了D{0-1}KP贪心核算法,设计了修复贪心核动态规划加速算法(RGCADP)、分段排序贪心核动态规划加速算法(RGCADP_PS)。两个算法在D{0-1}KP标准数据集上的实验结果表明:与基本动态规划算法(BDP)相比,RGCADP、RGCADP_PS算法平均求解时间提升率为71.3%、77.2%;RGCADP、RGCADP_PS算法平均解误差率低于粒子群贪心修复算法(PSO-GRDKP)0.5个百分点,低于贪心核加速动态规划(GCADP)算法4.7个百分点;RGCADP_PS时间性能提升率高于RGCADP算法5.9%。

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

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

贪心核加速动态规划算法精确求解适用范围

针对背包容量折扣系数在0.8~0.9时,贪心核加速动态规划算法(GCADP)无法求得逆向强相关折扣{0-1}背包问题实例(IDKP)精确解的问题,为求得D{0-1}KP实例的精确解,在对IDKP实例参数进行分析的基础上,给出GCADP算法能精确求解D{0-1}KP实例的限定条件:任意项集的价值系数满足价值最小项大于价值次大项的0.99倍。将该条件应用到4类D{0-1}KP实例的参数设置中,生成新的大规模D{0-1}KP实例。对4类D{0-1}KP实例运用GCADP和动态规划(DP)进行计算,计算结果表明,新的4类D{0-1}KP实例均得到精确解,并且GCADP随着数据规模的变大,求解时长增长平缓。