Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (7): 1912-1917.DOI: 10.11772/j.issn.1001-9081.2018112393

• Artificial intelligence • Previous Articles     Next Articles

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

SHI Wenxu<sup>1,2</sup>, YANG Yang<sup>3</sup>, BAO Shengli<sup>1,2</sup>   

  1. 1. University of Chinese Academy of Sciences, Beijing 100049, China;
    2. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu Sichuan 610041, China;
    3. School of Mathematics and Information, China West Normal University, Nanchong Sichuan 637009, China
  • Received:2018-12-05 Revised:2019-01-14 Online:2019-07-10 Published:2018-09-29
  • Supported by:

    This work is partially supported by the Key Research and Development Project of Sichuan Science and Technology Department (2018SZ0040), the College Students Innovation and Entrepreneurship Training Support Project of Sichuan Province (201810638085).

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

史文旭1,2, 杨洋3, 鲍胜利1,2   

  1. 1. 中国科学院大学, 北京 100049;
    2. 中国科学院 成都计算机应用研究所, 成都 610041;
    3. 西华师范大学 数学与信息学院, 四川 南充 637009
  • 通讯作者: 杨洋
  • 作者简介:史文旭(1995-),男,河南焦作人,硕士研究生,主要研究方向:智能算法、深度学习;杨洋(1993-),男,四川资阳人,硕士研究生,CCF会员,主要研究方向:数学建模、智能算法;鲍胜利(1973-),男,安徽黄山人,正研级高级工程师,博士,主要研究方向:智能信息处理、智能算法、深度学习。
  • 基金资助:

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

Abstract:

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).

Key words: Discounted {0-1} Knapsack Problem (D{0-1}KP), Greedy Core Acceleration Dynamic Programming (GCADP) algorithm, New Greedy Repaired Optimization Algorithm(NGROA), core algorithm, Basic Dynamic Programming (BDP)

摘要:

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

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

CLC Number: