一种用于求解0-1背包问题的动态伸缩算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (4): 47-49.

一种用于求解0-1背包问题的动态伸缩算法

拓守恒1，周涛2

1.陕西理工学院数学与计算机科学学院，陕西汉中 723000
2.宁夏医科大学理学院，银川 750004

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-02-01 发布日期:2012-04-05

New algorithm of solving 0-1 knapsack problem based on dynamic telescopic strategy

TUO Shouheng1, ZHOU Tao2

1.School of Mathematics and Computer Science, Shaanxi University of Technology, Hanzhong, Shaanxi 723000, China
2.School of Science, Ningxia Medical University, Yinchuan 750004, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-02-01 Published:2012-04-05

摘要/Abstract

摘要： 针对0-1背包这个非确定多项式（NP）完全难题，提出一种新的启发式搜索算法来解决0-1背包问题。算法采用多维实数编码，将物品按价值/重量比从大到小排序装包，通过用启发式策略选择交换背包内和背包外物品的位置，采用动态伸缩策略调整背包大小，选取种群中部分优秀解进入下一代继续进行优化。通过5个背包实例进行测试，实验结果表明该算法收敛速度快、求解精度高，并且具有良好的稳定性。

关键词: 0-1背包问题, 实数编码, 启发式搜索算法, 动态伸缩调整策略

Abstract: In order to solve the 0-1 knapsack NP-complete problem, a new heuristic search algorithm is proposed. Algorithm is encoded with the multi-dimensional real-coded. According to the cost per unit weight, it sorts the items in a decreasing order, and in this order the items are put into knapsack until can’t be installed. The algorithm exchanges the item’s positions of the inside and outside knapsack with a heuristic algorithm. Algorithm adjusts the items in the knapsack with a dynamic telescopic strategy and gets a better solution to the future generation. This algorithm is tested on 5 classic experiments, and the result shows that it has some advantages in convergence velocity, solution precision and stabilization.

Key words: 0-1 knapsack problem, real code, heuristic search algorithm, dynamic telescopic strategy

拓守恒1，周涛2. 一种用于求解0-1背包问题的动态伸缩算法[J]. 计算机工程与应用, 2012, 48(4): 47-49.

TUO Shouheng1, ZHOU Tao2. New algorithm of solving 0-1 knapsack problem based on dynamic telescopic strategy[J]. Computer Engineering and Applications, 2012, 48(4): 47-49.

[1]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[2]	袁明新1，2，谢丰1，姜烽1，江亚峰2. 基于精英集聚效应的实数编码小世界优化算法[J]. 计算机工程与应用, 2019, 55(10): 61-66.
[3]	马莹1，王怀晓2，刘贺3，陈志龙1. 一种新的自适应量子遗传算法研究[J]. 计算机工程与应用, 2018, 54(20): 99-103.
[4]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[5]	梁平，刘明周. 一种多染色体交叉的小生境遗传算法[J]. 计算机工程与应用, 2016, 52(18): 162-166.
[6]	吴聪聪，贺毅朝，陈嶷瑛，刘雪静，才秀凤. 求解0-1背包问题的二进制蝙蝠算法[J]. 计算机工程与应用, 2015, 51(19): 71-74.
[7]	余娟，贺昱曜. 解决0-1背包问题的遗传分布估计算法[J]. 计算机工程与应用, 2014, 50(9): 12-16.
[8]	李枝勇，马良，张惠珍. 遗传变异蝙蝠算法在0-1背包问题上的应用[J]. 计算机工程与应用, 2014, 50(11): 49-52.
[9]	邱涤珊，黄维，黄小军，王慧林. 多类扰动下电子侦察卫星动态调度问题研究[J]. 计算机工程与应用, 2012, 48(5): 239-243.
[10]	孙怀影1，耿寅融1，单谦2. 求解0-1背包问题的一种新混合算法[J]. 计算机工程与应用, 2012, 48(4): 50-53.
[11]	王晓笛1，肖伟1，何灿2. 改进的蛙跳算法在多目标优化问题中的应用[J]. 计算机工程与应用, 2012, 48(30): 233-238.
[12]	何小锋，马良. 求解0-1背包问题的量子蚁群算法[J]. 计算机工程与应用, 2011, 47(16): 29-31.
[13]	邓长寿^1，2. 高维0-1背包问题的双种群角度调制DE算法[J]. 计算机工程与应用, 2010, 46(24): 45-47.
[14]	刘蕾,鲁华祥. 集合划分问题的分布估计求解[J]. 计算机工程与应用, 2009, 45(10): 130-132.
[15]	赵朝卿,胡小兵. 一种新的求解0-1背包问题的混合算法[J]. 计算机工程与应用, 2008, 44(18): 61-63.