| 0-1背包问题的贪心局部搜索算法研究 |
| |
| 引用本文： | 林宏.0-1背包问题的贪心局部搜索算法研究[J].闽江学院学报,2009,30(5):66-70. |
| |
| 作者姓名： | 林宏 |
| |
| 作者单位： | 闽江学院物理学与电子信息工程系,福建福州350108 |
| |
| 基金项目： | 闽江学院科技育苗基金项目 |
| |
| 摘 要： | 为了提高求解0-1背包问题的效率,提出了两种贪心局部搜索算法,分别称为固定候选算法和变化候选算法.算法都以有效的方式构造好的初始解,随后执行局部搜索对其进行解质量上的改进.实验结果表明了两种算法的有效性、可行性及与价值密度贪心算法相比的优越性,同时进一步看出两种算法中变化候选算法相对较优,能够取得更好的结果.
|
| 关 键 词： | 背包问题 NP问题 算法 贪心策略 局部搜索 |
The study on greedy local search algorithm of 0-1 knapsack problem |
| |
| LIN Hong.The study on greedy local search algorithm of 0-1 knapsack problem[J].Journal of Minjiang University,2009,30(5):66-70. |
| |
| Authors: | LIN Hong |
| |
| Institution: | LIN Hong(Department of Physics and Electronics Information Engineering,Minjiang University,Fuzhou,Fujian 350108,China) |
| |
| Abstract: | 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... |
| |
| Keywords: | knapsack problem NP problem algorithm greedy strategy local search |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
