摘 要： 背包问题是算法设计分析中的经典问题 ,本文主要通过对回溯法 、动态规划 、贪心算法和遗传算法的研究 ,比较这四种方法在求解背包问题时的优缺点。
关键词：背包问题；回溯法；动态规划；贪心算法；遗传算法
1.问题描述
背包问题 :给定 n种物品和一个背包。物品 i 的重量是 W i,其价值为 V i,背包的容量为 C。应如何选择装入背包的物品 ,使得装入背包中物品的总价值最大 ? 在选择装入背包的物品时 ,对每种物品 i只有两种选择,即装入背包为 1 或不装入背包为 0。不能将物品i装入背包多次 ,也不能只装入部分的物品 i。
2.求解 背包问题的常用算法
1. 回溯法 。
回溯法在包含问题的所有解的解空间树中 ,按照深度优先的策略 ,从根结点出发搜索解空间树 。回溯算法搜索至解空间树的任一结点时 ,总是先判断该结点是否肯定不包含问题的解 。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索 ,逐层向其祖先结点回溯 。否则 ,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根 ,且根结点的所有子树都已被搜索遍才结束 ) 。
(3)根据轮盘赌法进行个体选择 。
(4)进行交叉运算 ,随即选择一对个体产生一对有效交叉位置进行交叉运算 ,并计算新产生的个体的适应度值和约束条件值。如果新产生的个体重量大于背包容量 ,则对新产生的个体进行修正 ,放弃在一个个体中的一个物品 ,增加另一个个体的一个物品使其重量小于背包重量 。
(5)进行变异操作 ,如果一个个体的一个基因为1 ,则变为0;如果是0则变为1 ,重新计算该个体的适应度值和约束条件值。
(6)选取具有最大值的适应度个体,如果其适应度大于当前的最优值的适应度 ,则更新当前的最优值为选取的个体 ,更新当前最优值的约束条件和迭代次数。
(7)循环迭代直到迭代次数超过设定最大值。
算法的时间复杂度为O( T*n2 ) ,其中T为迭代次数,n为种群个数。
3.算法比较
表 1 求解背包问题的算法比较
算法时间复杂度优点缺点改善回溯法O(n*2n )最优解速度慢剪枝动态规划O( n*m)最优解速度慢递归方程求解贪心算法O( n*logn )速度快不一定是最优解启发式方法遗传算法O( T*n2 )近似最优解速度慢，可能造成局部最优解惩罚方法和
译码方法
4.结束语
从计算复杂性理论看,背包问题是一个经典难解问题 。通过对背包问题的几种算法分析可以看出 ,回溯法能够精确地得到问题的最优解 ,可是付出了时间的代价 ; 动态规划算法也可以得到最优解 ,但当 m > 2n 时 ,算法需要 O ( n*2n ) 的计算时间 ,这与回溯法存在着一样的缺点———计算速度慢;采用贪心算法和遗传算法,虽然耗费上优于前者,但不一定能够得到最优解。目前,以上四
种方法都广泛地应用到不同的实际问题中,并在应用中不断地根据实际情况改进和完善。
参考文献 ：
[1]曾国清. 0-1背包问题的遗传算法求解 [ J ]. 科技信息 ,2006 ( 3 ) : 242 2243.
[2]黄与林. 0-1背包问题的贪心算法 [ J ]. 鄂州大学学报 , 2006 , 13 ( 6 ) : 38240.
[3]林鑫. 基于0-1背包问题的讨论 [ J ]. 微机发展 , 2005 , 15( 10 ) : 41243.
[4]史今驰.背包问题的实用求解算法研究 [ D ]. 济南:山东大学硕士学位论文, 2005.
