计算机工程与应用2012，Vol.48Issue(4)：47-49,3.DOI:10.3778/j.issn.1002-8331.2012.04.014
一种用于求解0-1背包问题的动态伸缩算法
New algorithm of solving 0-1 knapsack problem based on dynamic telescopic strategy
摘要
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.关键词
0-1背包问题/实数编码/启发式搜索算法/动态伸缩调整策略Key words
0-1 knapsack problem/ real code/ heuristic search algorithm/ dynamic telescopic strategy分类
信息技术与安全科学引用本文复制引用
拓守恒,周涛..一种用于求解0-1背包问题的动态伸缩算法[J].计算机工程与应用,2012,48(4):47-49,3.基金项目
国家自然科学基金(No.81160183) （No.81160183）
国家高技术研究发展计划(863)(No.2008AA01A303) （863）
陕西省教育厅科研基金(No.2010.JK459,2010JK466). （No.2010.JK459,2010JK466）
