一种全新的0-1背包问题的优化方法  

New optimization algorithm of 0-1 knapsack problem

作　　者：史岚[1] 吕建辉[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819

出　　处：《计算机应用研究》2014年第4期997-1000,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61100182)

摘　　要：为了进一步优化难解背包问题,在传统理论基础上给出了一种基于动态预期效率的经济学模型,构造了一种全新的背包优化算法,并进行了单独仿真实验和对比实验仿真。实验表明,在同一类背包问题中,该算法优于贪心算法、回溯法、动态规划算法和分支限界算法;与萤火虫群算法对比,该算法较大程度地提高了收敛速度并节省了存储空间,收敛速度几乎是萤火虫群算法的10倍。最后,经过对20个背包问题的探究,验证了该算法的可行性,并确定了该算法的适应范围。In order to do further research on enigmatical knapsack problems, this paper proposed an economic model based on dynamic expectation efficiency, and established a new optimization algorithm of 0-1 knapsack problem after analysis and re- search with the traditional theory of solving knapsack problem. And this paper gave the individual experiment and comparison experiment with artificial glowworm swam algorithm. The results of experiment show that the algorithm is better than greedy al- gorithm, backtracking algorithm, dynamic programming algorithm and bound algorithm in the same 0-1 knapsack problem. In comparison with artificial glowworm swam algorithm, this algorithm improves convergence speed largely and saves the storage space, and the convergence speed is ten times as the artificial glowworm swam algorithm. Finally, this paper gave 20 0-1 knapsack problems, proved the feasibility of the algorithm, and determined an adaptive scope of the algorithm.

关 键 词：0—1背包 动态预期效率 收敛速度 存储空间 适应范围 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]