0-1背包问题的贪心局部搜索算法研究

The study on greedy local search algorithm of 0-1 knapsack problem

为了提高求解0-1背包问题的效率,提出了两种贪心局部搜索算法,分别称为固定候选算法和变化候选算法.算法都以有效的方式构造好的初始解,随后执行局部搜索对其进行解质量上的改进.实验结果表明了两种算法的有效性、可行性及与价值密度贪心算法相比的优越性,同时进一步看出两种算法中变化候选算法相对较优,能够取得更好的结果.

In order to raise the efficiency of solving for 0-1 Knapsack Problem,two kinds of greedy local search algorithm of 0-1 KP are proposed,called fixed candidate algorithm and varying candidate algorithm.Each algorithm is used by effective method to construct good initial solution,and then carried out local search to gain availability.The result of experiments shows that each algorithm is effective,feasible and predominant with the comparative standard of value density greedy algorithm.Further,varying candidate algorithm is relatively optimized among the two algorithms and can obtain better result.