摘要
0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解.
The 0 - 1 knapsack problem is a typical kind of combinatorial optimization problems and is related to NP- complete, whose research has great significance. The greedy algorithm and the basic genetic algorithm for solving the 0 - 1 knapsack problem are introduced, and an improved genetic algorithm based on the greedy algorithm which is useful for solving the 0 - 1 knapsack problem is proposed. The experiment shows the result that the improved genetic algorithm can provide better approximate solutions.
出处
《云南民族大学学报（自然科学版）》
CAS
2008年第4期377-379,共3页
Journal of Yunnan Minzu University:Natural Sciences Edition
关键词
遗传算法
贪婪算法
0—1背包问题
genetic algorithm
greedy algorithm
0 -1 knapsack problem
