| 一种用于求解0-1背包问题的动态伸缩算法 |
| |
| 引用本文： | 拓守恒,周涛. 一种用于求解0-1背包问题的动态伸缩算法[J]. 计算机工程与应用, 2012, 48(4): 47-49 |
| |
| 作者姓名： | 拓守恒 周涛 |
| |
| 作者单位： | 1.陕西理工学院 数学与计算机科学学院，陕西 汉中 7230002.宁夏医科大学 理学院，银川 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 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
