| 一种用于求解0-1背包问题的动态伸缩算法 |
| |
| 引用本文： | 拓守恒,周涛.一种用于求解0-1背包问题的动态伸缩算法[J].计算机工程与应用,2012,48(4):47-49. |
| |
| 作者姓名： | 拓守恒 周涛 |
| |
| 作者单位： | 1. 陕西理工学院数学与计算机科学学院,陕西汉中,723000
2. 宁夏医科大学理学院,银川,750004 |
| |
| 基金项目： | 国家自然科学基金（No.81160183）;国家高技术研究发展计划（863）（No.2008AA01A303）;陕西省教育厅科研基金（No.2010JK459,2010JK466）. |
| |
| 摘 要： | 针对0-1背包这个非确定多项式(NP)完全难题,提出一种新的启发式搜索算法来解决0-1背包问题。算法采用多维实数编码,将物品按价值/重量比从大到小排序装包,通过用启发式策略选择交换背包内和背包外物品的位置,采用动态伸缩策略调整背包大小,选取种群中部分优秀解进入下一代继续进行优化。通过5个背包实例进行测试,实验结果表明该算法收敛速度快、求解精度高,并且具有良好的稳定性。
|
| 关 键 词： | 0-1背包问题 实数编码 启发式搜索算法 动态伸缩调整策略 |
| 修稿时间： | |
New algorithm of solving 0-1 knapsack problem based on dynamic telescopic strategy |
| |
| TUO Shouheng
,
ZHOU Tao.New algorithm of solving 0-1 knapsack problem based on dynamic telescopic strategy[J].Computer Engineering and Applications,2012,48(4):47-49. |
| |
| Authors: | TUO Shouheng ZHOU Tao |
| |
| Affiliation: | 1.School of Mathematics and Computer Science, Shaanxi University of Technology, Hanzhong, Shaanxi 723000, China2.School of Science, Ningxia Medical University, Yinchuan 750004, China |
| |
| Abstract: | In order to solve the 0-1 knapsack NP-complete problem, a new heuristic search algorithm is proposed. Algorithm is encod- ed 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 knap- sack 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. |
| |
| Keywords: | 0-1 knapsack problem real code heuristic search algorithm dynamic telescopic strategy |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
