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

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

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