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


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

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



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}背包问题, 贪心核加速动态规划算法, 新型贪心修复优化算法, 核算法, 基础动态规划

CLC Number: