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

doi:10.11772/j.issn.1001-9081.2018112393

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 Wenxu1,2, YANG Yang3, BAO Shengli1,2

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, 杨洋³, 鲍胜利^1,2

1. 中国科学院大学, 北京 100049;
2. 中国科学院成都计算机应用研究所, 成都 610041;
3. 西华师范大学数学与信息学院, 四川南充 637009

通讯作者: 杨洋
作者简介:史文旭(1995-),男,河南焦作人,硕士研究生,主要研究方向:智能算法、深度学习;杨洋(1993-),男,四川资阳人,硕士研究生,CCF会员,主要研究方向:数学建模、智能算法;鲍胜利(1973-),男,安徽黄山人,正研级高级工程师,博士,主要研究方向:智能信息处理、智能算法、深度学习。
基金资助:
四川省科技厅重点研发项目（2018SZ0040）；四川省大学生创新创业训练计划支持项目（201810638085）。

Abstract

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:

TP18

SHI Wenxu, YANG Yang, BAO Shengli. Greedy core acceleration dynamic programming algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications, 2019, 39(7): 1912-1917.

史文旭, 杨洋, 鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用, 2019, 39(7): 1912-1917.

References

[1] GUDER J. Discounted knapsack problems for pairs of items[D]. Nuremberg:University of Erlangen-Nurnberg, 2005.
[2] GULDAN B. Heuristic and exact algorithms for discounted knapsack prob1ems[D]. Nuremberg:University of Erlangen-Nuremberg, 2007.
[3] 贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630.(HE Y C, WANG X Z, Ll W B, et al. Research on genetic algorithms for the discounted {0-1} knapsack problem[J]. Chinese Journal of Computers, 2016, 39(12):2614-2630.)
[4] 杨洋,潘大志,刘益,等.折扣{0-1}背包问题的简化新模型及遗传算法求解[J].计算机应用,2019,39(3):656-662.(YANG Y, PAN D Z, LIU Y, et al. New simplified model of discounted {0-1} knapsack problem and solution by genetic algorithm[J]. Journal of Computer Applications, 2019, 39(3):656-662.)
[5] RONG A Y, FIGUEIRA J R, KLAMROTH K. Dynamic programming based algorithms for the discounted {0-1} knapsack problem[J]. Applied Mathematics and Computation, 2012, 218(12):6921-6933.
[6] HE Y C, WANG X Z, HE Y L, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem[J]. Information Sciences, 2016, 369(10):634-647.
[7] 杨洋,潘大志,贺毅朝.改进修复策略遗传算法求解折扣{0-1}背包问题[J].计算机工程与应用,2018,54(21):37-42.(YANG Y, PAN D Z, HE Y C. Improved repair strategy genetic algorithm solve discount {0-1} knapsack problem[J]. Computer Engineering and Applications, 2018, 54(21):37-42.)
[8] 杨洋,潘大志,贺毅朝.核加速遗传算法求解折扣{0-1}背包问题[J].西华师范大学学报(自然科学版),2018,39(2):165-172.(YANG Y, PAN D Z, HE Y C. Core accelerated genetic algorithm to solve the discount {0-1} knapsack problem[J].Journal of China West Normal University (Natural Sciences edition), 2018, 39(2):165-172.)
[9] FENG Y H, WANG G G, LI W, et al. Multi-strategy monarch butterfly optimization algorithm for discounted {0-1} knapsack problem[J]. Neural Computing and Applications, 2018, 30(10):3019-3016.
[10] 冯艳红,杨娟,贺毅朝,等.差分进化帝王蝶优化算法求解折扣{0-1}背包问题[J].电子学报,2018,46(6):1343-1350.(FENG Y H, YANG J, HE Y C, et al. Monarch butterfly optimization algorithm with differential evolution for the discounted {0-1} knapsack problem[J]. Acta Electronica Sinica, 2018, 46(6):1343-1350.)
[11] FENG Y H, WANG G G. Binary moth search algorithm for discounted {0-1} knapsack problem[J]. IEEE Access, 2018, 6:10708-10719.
[12] 刘雪静,贺毅朝,路凤佳,等.基于Lévy飞行的差分乌鸦算法求解折扣{0-1背包问题[J].计算机应用,2018,38(2):433-442.(LIU X J, HE Y C, LU F J, et al. Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem[J]. Journal of Computer Applications, 2018, 38(2):433-442.)
[13] 刘雪静,贺毅朝,路凤佳,等.基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题[J].计算机应用,2018,38(1):137-145.(LIU X J, HE Y C, LU F J, et al. Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem[J]. Journal of Computer Applications, 2018, 38(1):137-145.)
[14] 吴聪聪,贺毅朝,陈嶷瑛,等.变异蝙蝠算法求解折扣{0-1}背包问题[J].计算机应用,2017,37(5):1292-1299.(WU C C, HE Y C, CHEN Y Y, et al. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications, 2017, 37(5):1292-1299.)
[15] 刘雪静,贺毅朝,吴聪聪,等.基于细菌觅食算法求解折扣{0-1}背包问题的研究[J].计算机工程与应用,2018,54(2):155-162.(LIU X J, HE Y C, WU C C, et al. Research on bacterial foraging optimization algorithm for discounted {0-1} knapsack problem[J]. Computer Engineering and Applications, 2018, 54(2):155-162.)
[16] BALAS E, ZEMEL E. An algorithm for large zero-one knapsack problems[J]. Operations Research, 1980, 28(5):1130-1154.
[17] PISINGER D. Core problems in knapsack algorithms[J]. Operations Research, 1999, 47(4):570-575.
[18] PISINGER D. An expanding-core algorithm for the exact 0-1 knapsack problem[J]. European Journal of Operational Research, 1995, 87(1):175-187.
[19] BELLMAN R. Dynamic programming[J]. Science, 1966, 153(3731):34-37.
[20] MARTELLO S, PISINGER D, TOTH P. Dynamic programming and strong bounds for the 0-1 knapsack problem[J]. Management Science, 1999, 45(3):414-424.
[21] KATHRIN K, WIECEK M M. Dynamic programming approaches to the multiple criteria knapsack problem[J]. Naval Research Logistics, 2015, 47(1):57-76.
[22] BALEV S, YANEV N, FREVILLE A, et al. A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem[J]. European Journal of Operational Research, 2008, 186(1):63-76.
[23] DYER M E, RIHA W O, WALKER J. A hybrid dynamic programming/branch-and-bound algorithm for the multiple-choice knapsack problem[J]. Journal of Computational and Applied Mathematics, 1995, 58(1):43-54.
[24] MARTELLO S, TOTH P. Knapsack problems:algorithms and computer implementations[J]. Journal of the Operational Research Society, 1991, 42(6):513-513.
[25] GAREY M R, JOHNSON D S, STOCKMEYER L. Some simplified NP-complete graph problems[J]. Theoretical Computer Science, 1976, 1(3):237-267.
[26] KELLERER H, PFERSCHY U, PISINGER D. Knapsack Problems[M]. Berlin:Springer, 2004:1-17.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

[1]	XU Xiaoping, XU Li, WANG Feng, LIU Long. Learning monkey algorithm based on Lagrange interpolation to solve discounted ｛0-1｝ knapsack problem [J]. Journal of Computer Applications, 2020, 40(11): 3113-3118.
[2]	WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng. Mutated bat algorithm for solving discounted {0-1} knapsack problem [J]. Journal of Computer Applications, 2017, 37(5): 1292-1299.