背包问题的若干算法研究

《背包问题的若干算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁肈芁薅袃芄蕿薄羆肇蒅蚃肈节莁蚂螈肅芇蚁羀芀芃蚀肂膃薂虿螂荿蒈虿袄膂莄蚈羇莇芀蚇聿膀蕿螆蝿羃蒄螅袁膈莀螄肃羁莆螃螃芆节螃袅聿薁螂羇芅蒇螁肀肈莃袀蝿芃艿衿袂肆薈袈羄芁蒄袇膆肄蒀袇袆莀莆蒃羈膂节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁肈芁薅袃芄蕿薄羆肇蒅蚃肈节莁蚂螈肅芇蚁羀芀芃蚀肂膃薂虿螂荿蒈虿袄膂莄蚈羇莇芀蚇聿膀蕿螆蝿羃蒄螅袁膈莀螄肃羁莆螃螃芆节螃袅聿薁螂羇芅蒇螁肀肈莃袀蝿芃艿衿袂肆薈袈羄芁蒄袇膆肄蒀袇袆莀莆蒃羈膂节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀

2、葿薆肂芆莅薅螁肈芁薅袃芄蕿薄羆肇蒅蚃肈节莁蚂螈肅芇蚁羀芀芃蚀肂膃薂虿螂荿蒈虿袄膂莄蚈羇莇芀蚇聿膀蕿螆蝿羃蒄螅袁膈莀螄肃羁莆螃螃芆节螃袅聿薁螂羇芅蒇螁肀肈莃袀蝿芃艿衿袂肆薈袈羄芁蒄袇膆肄蒀袇袆莀莆蒃羈膂节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁背包问题的若干算法研究【摘要】本文主要通过若干算法来求解背包问题，同时比较各种算法的时间复杂度等性能的比较。【关键词】背包问题；贪心算法；遗传算法；动态规划;量子算法1问题描述0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装

3、入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包(1)或不装入背包(0)。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。背包问题可以描述为如下：假定有n个物体和一个背包，物体i的质量为wi，价值为pi，而背包的容量为M。若将物体i的一部分xi（1<=i<=n,0<=xi<=1)装入背包中，则有价值pi*xi。在约束条件（w1*x1+w2*x2+…………+wn*xn)<=M下使目标(p1*x1+p

4、2*x2+……+pn*xn)达到极大，此时满足0<=xi<=1,pi>0,1<=i<=n.2．贪心算法求解0-1背包问题贪心算法是一种改进了的分级处理算法，它每次都一步一步的进行，根据某个优化目标保证每一步的局部最有解最优。贪心算法是从局部最优出发，最终得到整体最优，也就是结果最优。贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件。枚举剩下的数据与当前已经选取的数据组合获得的解中，提取其中能获得最优解的唯一的一个数据，加入结果集合中，直到剩下的数据不能再加入为止。对于一个问题只能用穷举法求解的问题，用贪心法求解能够获得问题次优解，此时贪心算法也是比

5、较好的算法。1）用贪心算法求解背包问题的策略(1)价值贪婪优先策略：从剩余的物品中，选取价值最大的可以装入背包的物品。此时，价值最大的优先被装入背包，然后装入下一个价值最大的物品，直到不能再装入剩下的每一个物品为止。但是这样不能保证最优解。例如：M=30,W=[20,15,15],P=[50,30,30],用价值贪婪优先策略求的解为[1,0,0],此时总价值为50，但最优解为[0,1,1]，此时总价值为60。(2)重量优先策略：从剩余的物品中选取重量最小的物品装入背包中，这种策略一般不能得到最有解。例如：M=20,W=[10,15],P=[20,30],用重量优

6、先策略求出的解为[1,0]，总价值为20，比最优解[0,1]的最优解差得多。(3)单位价值优先策略：就是根据Pi/Wi得比值，按照每一次选取剩下得物品中比值最大得物品装入背包。直到不能再装入为止。这种策略也不能保证得到最优解，但比最优解相差较小。如果可以选择物品的一部分，用单位价值策略可以保证得到最优解。另外一种改进的算法第一次把物品按照体积的从大到小的顺序放进包中。1973年，D.Johnson表明这种算法有22%的可能永远也不可能达到最优解，并且进一步指出没有有效的背包算法能够保证做到比22%还好(Hoffman1998,p.172[6])。贪心算法是通过局

7、部最优逐步过渡到整体最优，贪心算法的最优整体结构每一步都保证是最优子结构。贪心算法的时间复杂度为O(2^n).3．用动态规划求解0－1背包问题动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子问题中求出原问题的解。1）迭代求解：Value[i][j]表示前i件物品能装入容量为j的背包时背包中的总价值。若wivalue[i-1][j]，则把value[I][J]记录为当前最大价值。用迭代求解的算法描述如下：  for(i=1;i

8、(j=1;j