基于遗传算法求解0-1背包问题的算法探讨  

On the Algorithm of Solving the 0-1 Knapsack Problem Based on the Genetic Algorithm

作　　者：刘锐[1] 张金波[1] 刘蕊洁[1] 李积宪[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《云南民族大学学报（自然科学版）》2008年第4期377-379,共3页Journal of Yunnan Minzu University:Natural Sciences Edition

摘　　要：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.

关 键 词：遗传算法 贪婪算法 0—1背包问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]