摘要： 为求解多限制0-1背包问题，设计一种新的价值密度，提出一种基于贪心法的混合遗传算法，采用二进制编码对适应值进行升序排列，并运用轮盘赌选择方法对背包资源利用不足的可行解进行修正处理，对不可行解进行修复处理，并将其与传统遗传算法进行比较。实验结果表明，该算法能够有效提高问题求解的速度和精度，具有一定优越性。

关键词: 背包问题, 贪心法, 遗传算法, 不可行解

Abstract: In order to solve multi-constraint 0-1 knapsack problem, a new profit-density is designed, on basis of which, a Hybrid Genetic Algorithm(HGA) based on greedy algorithm is proposed, which uses the binary code to amend the feasible solution, and applies roulette wheel selection method to rectify knapsack resources with insufficient use, and repairs the infeasible solution. The algorithm is compared with other traditional ones. Experimental results show this HGA can promote the speed and accuracy of solving relevant problems efficiently, and is superior.

Key words: knapsack problem, greedy algorithm, Genetic Algorithm(GA), infeasible solution

中图分类号: 

• TP301.6