几种背包问题的算法分析与比较

《几种背包问题的算法分析与比较》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、几种背包问题的算法分析与比较背包问题是算法设计分析中的经典问题,本文主要通过对回溯法、动态规划、贪心算法和遗传算法的研究,比较这四种方法在求解背包问题时的优缺点。关键词：背包问题；回溯法；动态规划；贪心算法；遗传算法1.问题描述　　背包问题:给定n种物品和一个背包。物品i的重量是icprogramming)是运筹学的一个分支,是求解决策过程(decisionprocess)最优化的数学方法。二十世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisi

2、onprocess)的优化问题时,提出了著名的最优化原理(principleofoptimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系逐个求解,创立了解决这类过程优化问题的新方法———动态规划[6]。　　动态规划算法的基本思想是把原问题分解成一系列子问题,然后从这些子问题中求出原问题的解。对一个负重能力为m的背包,如果选择装入一个第i种物品,那么原背包问题就转化为负重能力为m-),其中n为物体的个数,m为背包负重。3.贪心算法。　　贪心算法是一种改进了的分级处理算法,根

3、据某个优化目标保证每一步都有局部最优解。贪心算法每次只考虑一步,每一步数据的选取都必须满足局部最优条件。枚举剩下的数据与当前已经选取的数据组合获得的解中,提取其中能获得最优解的唯一的一个数据,加入结果集合中,直到剩下的数据不能再加入为止。　　在求解背包问题时,对贪心算法可以使用一些策略，使其得到的解更接近最优解。具体方案如下:(1)价值优先策略[5]:从剩余的物品中,选取价值最大的可以装入背包的物品。此时,价值最大的优先被装入背包,然后装入下一个价值最大的物品,直到不能再装入剩下的物品为止。(2

4、)重量优先策略[5]:从剩余的物品中选取重量最小的物品装入背包中,这种策略一般不能得到最优解。(3)单位价值优先策略[5]:根据价值/重量的比值,按照每次选取剩下的物品中比值最大的物品装入背包,直到不能再装入为止。　　在贪心算法时间复杂度的估算中,由于需要对重量或价值或两者的比值进行排序,所以贪心算法的时间复杂度为O(n*logn)。4.遗传算法。　　遗传算法(GeicAlgorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法[2]。

5、遗传算法的一般步骤:确定二进制编码取值范围,初始化染色体的个数,并随机产生所有的染色体,计算个体的适应度,经过交叉运算和变异操作,进行遗传迭代求解。　　　　背包问题的遗传算法求解策略[8]:　　　　将物品根据单位重量价值从大到小排序。　　用0和1分别表示物品i放入背包和物品i不放入背包,如果Xi表示物品i是否放入背包,则:　　　　放入背包的总重量为)最优解速度慢递归方程求解贪心算法O(n*logn)速度快不一定是最优解启发式方法遗传算法O(T*n2)近似最优解速度慢，可能造成局部最优解惩罚方法和

6、译码方法　　4.结束语　　从计算复杂性理论看,背包问题是一个经典难解问题。通过对背包问题的几种算法分析可以看出,回溯法能够精确地得到问题的最优解,可是付出了时间的代价;动态规划算法也可以得到最优解,但当m>2n时,算法需要O(n*2n)的计算时间,这与回溯法存在着一样的缺点———计算速度慢;采用贪心算法和遗传算法,虽然耗费上优于前者,但不一定能够得到最优解。目前,以上四种方法都广泛地应用到不同的实际问题中,并在应用中不断地根据实际情况改进和完善。