0-1背包问题多算法比较

计算机科学与技术学院算法分析2013年6月2日星期日计算及自动化容中宇201126630615浙江工业大学计算机学院0-1背包问题多算法算法与分析计算机科学与技术学院算法分析2013年6月2日星期日计算及自动化容中宇2011266306150-1背包问题多算法分析与比较容中宇（浙江工业大学计算机科学与技术学院，浙江，杭州，310023）摘要：经过一个学期对计算机算法设计与分析这门课的学习，对计算机语言在算法与实现等诸多方面有了一个全新的认识。在很多问题当中，从前的思路和经验只适合于初级编程者。随着计算机相关领域对计算机算法计算时间的不断严苛要求，对于算法的优化成为现相关研究的主流。0-1背包问题是诸多算法的典型范例，多种算法的比较中，可以看到各自的优缺点，而从其中引申出来的算法可以很好地应用到其他问题的求解当中。关键词：0-1背包问题；多算法；中图分类号：TPXXX文献标识号：A文章编号：（2013）0引言背包问题(Knapsackproblem)是一种组合优化的NP完全问题。它是在1978年由Merkel和Hellman提出的。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？StonyBrook大学1998年的一项研究表明，出75的算法问题，背包问题是18最流行的和最需要的第四KD-树，后缀树，装箱问题[1]。背包问题出现在现实世界的决策过程中的各种领域，如发现至少浪费的方式来减少原材料，[2]选择资本投资和金融投资组合，[3]选择资产资产证券化，[4]梅克尔-Hellman背包密码生成密钥。[5]背包算法的一个早期应用是在建设和测试的测试者有一个选择的问题，他们的回答得分。对于小的例子，它是一个相当简单的过程，测试者提供这样的选择。例如，如果考试包含12个问题，每个价值10点，测试者只需要回答10个问题，以实现最大可能分值为100分。然而，在测试与异构分布的点值，即不同的问题都值得不同的点值，提供的选择是比较困难的。Feuerman和Weiss提出了一种系统，在该系统中，学生给出异构测试，总的125个可能的点。学生们被要求回答所有的问题，自己最大的能力。可能的问题的总点值高达100的子集，背包算法将确定哪个子给每个学生的最高分。由以上这些可以看出，0-1背包问题计算机科学与技术学院算法分析2013年6月2日星期日计算及自动化容中宇201126630615在现实世界中的应用是极其广泛的。研究透它，可以为我们解决其他问题找到捷径。1预备知识在以下文章当中，会用带的算法列举。算法一：动态规划（knapsackproblems）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。算法二：回溯法（backtracking）是暴力搜寻法中的一种。回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：找到一个可能存在的正确的答案在尝试了所有可能的分步方法后宣告该问题没有答案在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。算法三：分支限界法分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2基于0-1背包问题的算法实现2-1动态规划算法2-1-1算法描述动态规划应用在0-1背包问题当中，重点体现在，将大的问题细化，并将细化之后重复的计算结果存入一个二维表当中，方便以后出现重复要求是的快捷调用。1.动态规划法用于求解非最优化问题：当问题实例P(n)的解由子问题实例的解构成时，比如P(n)=P(n-1)+P(n-2)[斐波那契数列]，而P(n-1)和P(n-2)可能包含重合的子问题，可以使用动态规划法，通过自底向上的迭代，求解较小子问题实例的解，并作为求解较大子问题实例的解的基础。关键思想是：避免对子问题重复求解。比如：求斐波那契数F(5)：F(5)=F(4)+F(3);子问题：F(4)=F(3)+F(2);F(3)=F(2)+F(1);F(2)=F(1)+F(0)计算机科学与技术学院算法分析2013年6月2日星期日计算及自动化容中宇201126630615F(2)=F(1)+F(0);子问题：F(3)=F(2)+F(1)F(2)=F(1)+F(0)由上面的计算过程可知，如果单纯使用递归式，则子问题F(2)被重复计算了2次；当问题实例较大时，这些重复的子问题求解就会耗费大量不必要的时间。若使用动态规划法，将F(2)的值存储起来，当后续计算需要的时候，直接取出来，就可以节省不少时间。2-1-2算法实现根据以上描述，关键点是构造一个二维向量表m[*][*]，其中用于存储结果。两种算法函数。TemplateclassTypeKnapsack(v,*w,c,n,**m)//此函数用于计算每一种可能的向量结果{for(inti=1;i=n;i++)m[i][i]=0;for(intr=2;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}Traceback(m,w,c,n,x)//最优解计算{for(inti=1;in;i++)if(m[i][n]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]==(m[n][c])?1;0;//设置最优解}2-2回溯法2-2-1算法描述回溯法求解0-1背包问题，是以原点为基础，以一颗解空间树为数据模型，以深度搜索为搜索模式的算法，其最终将整棵树搜索完毕，每次搜索可能解都与当前最优解比较，如果优于当前最优解，则替换。若非，则不做任何改动。2-2-2算法实现以类Knap作为树的每一节点[6]Backtrack(inti)//计算当前节点做拓扑{if(in)//到达叶节点回溯{}if(cw+w[i]=c)//进入左子树{……Backtrack(i+1);//当前节点拓展……}if(Bound(i+1)bestp)//进入右子树}Bound(inti)//剪支函数{…If(i=n)b+=p[i]*cleft/w[i];…}2-3分支限界法2-3-1算法描述分支限界法在0-1背包问题中，主要是以广度优先的方法，其中用一个优先队列做为活节点的容器，当扩展节点时，从优先队列当中取出节点，直到队列当中为空。2-3-2算法实现计算机科学与技术学院算法分析2013年6月2日星期日计算及自动化容中宇201126630615与回溯法相似的，以类Knap做为节点属性载体。MaxKnapsack()//优先队列实现{H=newMaxHeapHeapNodeTypep,Typew(1000);Bestx=newint[n+1];Inti=1;E=0;cw=cp=0;Typep=bestp=0;Typepup=bound(1);While(1!=n+1){Typewwt=cw+w[i];If(wt=c)//左儿子节点可行{if(cp+p[i]bestp)bestp=cp+p[i];addliveNode(up,cp+p[i],cw+w[i],true,i+1)；}up=bound(i+1);If(up=bestp)//右儿子节点可行{addliveNode(up,cp,cw,false,i+1);HeapNodeTypep,TypewN;H-deleteMax(N);…}}3算法比较分析动态规划：算法K的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)回溯法：计算上界许o(n),而坏情况下有O(2^n)右孩子，平均时间要O(n2^n)分支限界法：相对来讲，分支限界法找到的最优解不是全局性的。4结束语通过对0-1背包问题的讨论，可以发现很多问题解决的思路是多样的。每一种是最好的，每一个问题的求解都有它各自的求解环境。这三个算法没有那一种是最好的，之后那一种是更符合实际要求的。参考文献：[1].Skiena,S.S.(September1999).WhoisInterestedinAlgorithmsandWhy?LessonsfromtheStonyBrookAlgorithmRepository.AGMSIGACTNews30(3):65–74.ISSN0163-5700.[2].Kellerer,Pferschy,andPisinger2004,p.449[3].Kellerer,Pferschy,andPisinger2004,p461[4].Kellerer,Pferschy,andPisinger2004,p465[5].Kellerer,Pferschy,andPisinger2004,p472[6].王晓东，计算机算法设计与分析[M]，北京：电子工业出版社，2004