基于绝对贪心和预期效率的0-1背包问题优化  

Optimization algorithm of 0-1 knapsack problem based on absolute greedy and expected efficiency

作　　者：史岚[1] 张义宏[1] 吕建辉[1] 

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

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

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

摘　　要：在传统求解背包问题的理论基础之上,对难解背包问题进行优化,设计了一种基于绝对贪心策略和预期效率的新算法。针对该算法进行了三组仿真实验,结果表明,算法能够较好地解决一类0-1背包问题,优于贪心算法、回溯法、动态规划算法、分支限界算法,该算法的收敛速度是萤火虫群算法的10倍。经过分析数据的离散程度,确定了该算法的适应范围。With analysis and research the traditional theory of solving knapsack problem, and then to optimize enigmatical knap- sack problems, this paper proposed a new algorithm based on the absolute greedy and expected efficiency strategy. Through the three sets of simulation experiments, it shows that the algorithm can solve a class of knapsack problems and it is superior to greedy algorithm, backtracking algorithm, dynamic programming algorithm, branch and bound algorithm. The convergence speed is ten times as the artificial glowworm swam algorithm by comparing with these two algorithms. Finally, it analyzed discrete degree of da- ta and determined an adaptive scope of the algorithm.

关 键 词：0-1背包问题 绝对贪心 预期效率 收敛速度 离散程度 

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