背包问题的若干算法研究.doc

节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁肈芁薅袃芄蕿薄羆肇蒅蚃肈节莁蚂螈肅芇蚁羀芀芃蚀肂膃薂虿螂荿蒈虿袄膂莄蚈羇莇芀蚇聿膀蕿螆蝿羃蒄螅袁膈莀螄肃羁莆螃螃芆节螃袅聿薁螂羇芅蒇螁肀肈莃袀蝿芃艿衿袂肆薈袈羄芁蒄袇膆肄蒀袇袆莀莆蒃羈膂节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁肈芁薅袃芄蕿薄羆肇蒅蚃肈节莁蚂螈肅芇蚁羀芀芃蚀肂膃薂虿螂荿蒈虿袄膂莄蚈羇莇芀蚇聿膀蕿螆蝿羃蒄螅袁膈莀螄肃羁莆螃螃芆节螃袅聿薁螂羇芅蒇螁肀肈莃袀蝿芃艿衿袂肆薈袈羄芁蒄袇膆肄蒀袇袆莀莆蒃羈膂节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁肈芁薅袃芄蕿薄羆肇蒅蚃肈节莁蚂螈肅芇蚁羀芀芃蚀肂膃薂虿螂荿蒈虿袄膂莄蚈羇莇芀蚇聿膀蕿螆蝿羃蒄螅袁膈莀螄肃羁莆螃螃芆节螃袅聿薁螂羇芅蒇螁肀肈莃袀蝿芃艿衿袂肆薈袈羄芁蒄袇膆肄蒀袇袆莀莆蒃羈膂节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁 背包问题的若干算法研究【摘要】本文主要通过若干算法来求解背包问题，同时比较各种算法的时间复杂度等性能的比较。【关键词】 背包问题；贪心算法；遗传算法；动态规划; 量子算法 1问题描述0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包(1)或不装入背包(0)。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。背包问题可以描述为如下：假定有n个物体和一个背包，物体i 的质量为wi，价值为pi，而背包的容量为M。若将物体i的一部分xi（1=i=n,0=xi=1)装入背包中，则有价值pi*xi。在约束条件（w1*x1+w2*x2+wn*xn)=M下使目标(p1*x1+p2*x2+pn*xn)达到极大，此时满足0=xi0,1=i=n.2贪心算法求解0-1背包问题贪心算法是一种改进了的分级处理算法，它每次都一步一步的进行，根据某个优化目标保证每一步的局部最有解最优。贪心算法是从局部最优出发，最终得到整体最优，也就是结果最优。贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件。枚举剩下的数据与当前已经选取的数据组合获得的解中，提取其中能获得最优解的唯一的一个数据，加入结果集合中，直到剩下的数据不能再加入为止。对于一个问题只能用穷举法求解的问题，用贪心法求解能够获得问题次优解，此时贪心算法也是比较好的算法。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,用重量优先策略求出的解为1,0，总价值为20，比最优解0,1的最优解差得多。 (3)单位价值优先策略：就是根据Pi/Wi得比值，按照每一次选取剩下得物品中比值最大得物品装入背包。直到不能再装入为止。这种策略也不能保证得到最优解，但比最优解相差较小。如果可以选择物品的一部分，用单位价值策略可以保证得到最优解。另外一种改进的算法第一次把物品按照体积的从大到小的顺序放进包中。1973年，D. Johnson表明这种算法有22%的可能永远也不可能达到最优解，并且进一步指出没有有效的背包算法能够保证做到比22%还好(Hoffman 1998,p.1726)。贪心算法是通过局部最优逐步过渡到整体最优，贪心算法的最优整体结构每一步都保证是最优子结构。贪心算法的时间复杂度为O(2n).3用动态规划求解01背包问题 动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子问题中求出原问题的解。1）迭代求解： Valueij表示前i件物品能装入容量为j的背包时背包中的总价值。若wij则第i件物品不装入，否则，若wivaluei-1j，则把valueIJ记录为当前最大价值。 用迭代求解的算法描述如下：for(i=1;irow;i+).for(j=1;jj,第i个物品不装入背包 valueij=valuei-1j;/wivaluei-1j,则修改当前的最大价值Int temp=valuei-1j-wi+vi;if(wivalueij) valueij=temp; 算法的时间复杂度为O(n*m),n为物品个数，m为背包容量。 2） 递归求解：背包问题的最优决策序列是由最优决策子序列组成。根据最优决策序列的最优决策子序列的结构，可得到如下的递归式：假设valueij表示容量为j，剩余物品为I,i+1,i+2,n时的最有解，当j=wi时： valueij=max(valuei+1j,valuei+1j-wi+pi 当0=jwi时：valueij=valuei+1j value1w 是初始时背包问题的最优解。这种算法的时间复杂度为O（n*2n）.4.用回溯法求解背包问题： 回溯其实就是穷举，穷举所有的解，找出解中最优的值。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。回溯算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法在求解空间树时，只要其左儿子节点时一个可行结点时就进行该左子树，只有右子树包含可行解时才进入右子树，否则就剪去右子树。 回溯法的基本思路是：确定解空间，建立解空间树，用深度优先搜索算法递归搜索解空间树，并同时注意剪枝。 背包问题的算法思路：按照物品的单位价值从大到小排序，计算当前节点的上界，搜索左子树，如果右子树包含可行解，就搜索右子树。剪去右子树条件：当前价值加上剩余物品的总价值小于当前的最优总价值时，不需搜索右子树，可将右子树剪去。用回溯法求解背包问题的伪代码：void Backtrack(int i)如果已经搜索完一条从根节点到叶节点的路径，更新当前解的最优值bestp；如果左节点的重量小于剩余的背包重量，进入左子树进行搜索；如果右子树包含当前解，进入右子树进行搜索。否则剪去右子树。回溯法实际时穷举算法，用一定的剪枝进行优化，算法的时间复杂度为O(n*2n)，n为物品个数。4遗传算法求解01背包问题：遗传算法是计算数学中用于解决最优化的搜索算法，是一种进化算法。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。通常解用二进制0和1表示，进化从一个个体发生，然后一代一代发生。在每一代中，该种群的价值被评估，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。遗传算法的一般步骤：确定二进制编码取值范围，初始化染色体的个数，并随机产生所有的染色体，构造评价函数和个体的适应度总和，经过交叉运算和变异操作，进行遗传迭代求解。01背包问题的遗传算法求解策略：(1)二进制法策略：将物品根据单位重量价值从大到小排序。用0和1分别表示物品i放入背包和物品i不放入背包，如果Xi表示物品i是否放入背包，则放入背包的总重量为w=w1*x1+w2*x2+wn*xn;放入背包的物品的总价值为P=p1*x1+p2*x2+pn*xn。Fm存放目标函数值就是个体的适应度。Tn存放每个个体的约束条件值1） 初始种群产生，并计算每个适应度值和其对应的约束条件值(即为染色体中选取的物品的重量)，比较初始种群中各个个体的适应度。选择最大者所对就的个体作为第一代最优个体并记录该个体以及它的适应度和约束条件值。2） 计算每个个体的选择概率PiFi/E(Fi)3） 根据轮盘睹法进行个体选择；4） 进行交叉运算，随即选择一对个体产生一对有效交叉位置进行交叉运算，并计算新产生的个体的适应度值和约束条件值,如果新产生的个体重量大于背包容量，则对新产生的这个个体进行修正，放弃在一个个体中的一个物品，增加另一个个体的一个物品使其重量小于背包重量。5） 进行变异操作，如果一个个体的一个基因为1，则变为0，如果使0则变为1，重新计算该个体的适应度和约束值。6） 选取具有最大值的适应度个体，如果其适应度大于当前的最优值的适应度，则更新当前的最优值为选取的个体，更新当前最优值的约束条件和迭代次数。7） 循环迭代直到迭代次数超过设定最大值。算法的时间复杂度为O(N*n2)N为迭代次数，n为物品个数5 量子算法求解01背包问题 量子算法从概率算法出发，系统由一个状态转移到另一个状态有一个状态几率矢量，通过状态几率矢量和状态转移矩阵得到下一个状态。长度为 的量子字节串A1n在 1-n中Ai=Xi (xi (O，1 )则 A显然有N2 种状态用量子算法求解背包问题的步骤如下：1.给定常数c，井随机选取A的N种状态在N种状态中选择最大的Y=Ai*Pi.且 wi*PiW2. 重复下列操作 c次2.1对2n个状态给定初始几率幅均为(1/N, 1/N,-, 1/N),并将y绑定在一起，满足1条件的做标记。2.2.1给定常数m=1并且r=6/5 2.2.2随机选取非负整数 jy且重量小于背包重量，则y状态的值改为y1退出 2.2. 2.2.6否则 mmin(r, N)，goto 2.2.2 3得到最优解 Y量子算法的时间复杂度为O(C*2n)c为重复的次数。6分枝限界法求解背包问题： 常用的分枝一限界法有最小耗费法，最大收益法FIFO(先进先出)法等。01背包问题的分枝一限界算法可以使用最大收益算法。该算法跟回溯法类似。但分枝限界法需要O(2n)的解空间。故该算法不常用在背包问题求解。7各种算法的比较：算法名称时间复杂度优点缺点改进贪心算法O(2n)速度快不能保证得到最优解启发式方法动态规划O(n2)可求得最优解速度慢些递归方程求解回溯法O(n*2n)可求得最优解速度慢剪枝遗传算法O(n*2n)可求得最优解速度慢，不成熟惩罚方法和译码方法量子算法O(c*2n)不能保证求得最优解算法不成熟，速度慢选取迭代次数优化分枝限界法O(2n)速度快占用内存空间大最大收益法8结束语以上是对背包问题求解的多种算法分析和比较，并对各种算法的改进进行分析。【参考文献】1 T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introduction to Algorithms (the second edition). The MIT Press，中文名算法导论（第二版）（影印版），高等教育出版社2郭晓军 遗传算法在求解背包问题中的应用 大连铁道学院学报 22卷第3期2001.93陈文兰 刘建华 个求解O一1背包问题的遗传算法 福建电脑 第五期 20064胡劲松 陈国良 郭光灿 在量子计算机上求解01背包问题 计算机学报22卷12期 1999.12 袀肃莇蚆肆莁莆螈衿芇莅袀肄膃蒄薀袇聿蒃蚂肂羅蒂螄袅莄蒁薄膁芀蒁蚆羄膆蒀蝿腿肂葿袁羂莁蒈薁螅芇薇蚃羀膃薆螅螃肈薅蒅羈羄薅蚇螁莃薄螀肇艿薃袂袀膅薂薁肅肁薁蚄袈莀蚀螆肃芆虿袈袆膂虿薈肂膈芅螀袄肄芄袃膀莂芃薂羃芈芃蚅膈膄节螇羁肀莁衿螄荿莀蕿罿芅荿蚁螂芁莈袄羈膇莇薃袀肃莇蚆肆莁莆螈衿芇莅袀肄膃蒄薀袇聿蒃蚂肂羅蒂螄袅莄蒁薄膁芀