10,1背包问题的应用

1、J孝数学与计算机学院课程设计说明书课程名称：算法设计与分析-课程设计课程代码：7106620题目:0/1背包问题的应用年级/专业/班:学生姓名：学号：开始时间：2010年12月27日完成时间：2011年01月07日课程设计成绩：学习态度及平时成绩(30)技术水平与实际能力(20)创新(5)说明书撰写质量(45)总分(100)指导教师签名：年一月日目录11111111111111111111111111111111111111引言1111111111111111111111111111111111121.1 问题的提出111111111111111111111111111111121.2 背包问

2、题的研究现状11111111111111111111111111121.3 求解0-1背包问题常见方法11111111111111111111111131.4 算法设计与分析的地位1111111111111111111111111131.5 动态规划的基本思想11111111111111111111111111131.6 分支界限法的基本思想1111111111111111111111111141.7 任务与分析111111111111111111111111111111142 设计方案11111111111111111111111111111111142.1 问题描述111111111111

3、1111111111111111111142.2 算法描述和设计1111111111111111111111111111142.2.1 动态规划法11111111111111111111111111111142.2.2 分支界限法11111111111111111111111111111152.3 详细设计1111111111111111111111111111111152.4 算法编码实现11111111111111111111111111111163 程序运行平台111111111111111111111111111111144 .系统测试1111111111111111111111111

4、1111111144.1 测试数据1111111111111111111111111111111154.2 测试结果1111111111111111111111111111111154.3 程序运行结果11111111111111111111111111111154.4 算法的时间复杂度分析111111111111111111111111116结论，11718m11111111111111111111111111111111111参考文献1911、II，、，摘要针对一类难解的0/1背包问题，揭示了该类问题和子集和数问题的相似性，及该类问题特有的属性；描述了最大价值的获得与物品集中元素的组合相关

5、性。在价值密度比贪心策略基础上设计了一个搜索算法。实验表明，在多项式时间复杂度内得到的解的质量优于目前最好算法的结果。本文算法的最优解与物品集中元素的重量和价值参数的大小分布无关，而只与元素的重量及背包零头的组合相关，因而具有相当的竞争力。0/1背包问题是实际当中经常遇到的一类经典NP-hard组合优化问题之一。本文分别从贪心方法、动态规划、回溯法、分支限界法，遗传算法这五种算法设言十方法入手，概述了各种设计方法的基本原理，提出了求解0/1背包问题的算法思想，并对算法进行分析，提出了改进方法。关键词：0/1背包问题；动态规划；分支限界法1引言对于计算机科学来说，算法的概念是至关重要的。在一个大

6、型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，算法分析与设计成为计算科学的核心问题之一，也是信息与计算科学专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”与“坏”，怎样设计算法，并以广泛用于计算机科学中的算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。1.1 问题的提出它是在

7、1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密的选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品时保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算机上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度的快而其人注目。在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是经典的应用例子。随着网络技术的不断发展，背包公钥密码在电

8、子商务中的公钥设计中叶起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。但是，大多数一次背包体制均被破译了，因此现在很少人使用它。背包问题是一种组合优化的NP完全问题。问题可以描述为：在杂货店中有n种不同的货物。现将货物装车，规定从每种货物中最多只能拿一件，车子的容量为W物品i需要占用Wi的空间，价值为Vi。现要求设计算法和程序使车中装载的物品价值最大。当然,所装货物不能超过车的容量，且同一种物品不得拿走多件。1.2 背包问题的研究现状Dantzing在20世纪50年代首先进行了开创性的研究，利用贪婪算法求得了0-1背包问题最优解的上界。1974年，horowitz和salmi利

9、用分支界限法解答背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。随后，balas和zemel提出了背包问题的“核”思想，使背包问题的研究获得了较大进展。上世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例如遗传算法已经在0/1背包问题上得到较好的应用，蚂蚁算法等仿生算法也在组合优化问题中得到了很好的应用。1.3 求解0-1背包问题常见方法传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等，由于精确算法的时间复杂性和空间复杂性等缺

10、点，近年来利用近似算法求解背包问题成为重点。本次课程设计，我们主要用动态规划法和分支界限法来求解该背包问题。1.4 算法设计与分析的地位算法设计与分析在计算机科学中是一门综合性的专业基础课。算法的研究不仅涉及到计算机硬件(特别是编码理论、存储装置和存取方法等)的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为算法设计与分析是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，算法设计与分析不仅是一般程序设计的基础，而且是设

11、计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。1.5 动态规划的基本思想动态规划法是上世纪50年代RichardBellman创建的解决多阶段决策过程最优化的一种数学方法，即把多阶段决策问题变换为一系列相互联系单阶段问题，然后逐个加以解决。它的特点是解决多阶段、离散性问题。动态规划算法的基本思想是把原问题分解成一系列子问题，然后从这些子问题中求出原问题的解。对一个负重能力为C的背包，如果选择装入第i种物品，那么原背包问题就转化为负重能力为C-ci的子背包问题。动态规划算法是一种经典的背包问题求解算法，其原理简单，算法思路清晰，易于实现。动态规划算法虽然高效，但是

12、对于规模较大的问题它不是一个理想的算法，主要原因就是它的维数障碍，即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。动态规划算法的时间复杂度为o(min(nC,2An),其中n为物体的个数,C为背包负重。精确算法的优点是当问题规模较小时一定可以求得最优解，缺点是当问题规模较大时因计算量太大而无法实现。所以一些学者提出了各种近似算法来解决精确算法求解背包问题时的时间复杂性和空间复杂性难题。1.6 分支界限法的基本思想用分支界限算法求解背包问题具有相当不寻常的特征。一般来说，一棵状态空间树的中间节点并不能确定问题的查找空间中的一个点，因为解得某些分量还未明确。然而，对于背包问题

13、来说，树的每一个节点都可以代表给定物品的一个子集。在生成了树中的每一个新节点之后，我们可以利用这个事实，来更新目前为止的最佳子集信息。1.7 任务与分析1 .给出多种求解算法，如动态规划法、贪婪法。2 .编程实现所给算法。3 .对所写算法给出时间空间复杂性分析。2设计方案2.1 问题描述在杂货店中有n种不同的货物。现将货物装车，规定从每种货物中最多只能拿一件，车子的容量为W物品i需要占用Wi的空间，价值为Vi0现要求设计算法和程序使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。2.2 算法描述和设计本实验主要是运用动态规划法和分支界限法解0/1背包问题。算法

14、分析如下：2.2.1 动态规划法：我们可以把前i个物品中能够放进承重量为j的背包中的子集分成两个类别：包括第i个物品的子集和不包括第i个物品的子集。有下结论：1 .根据定义，在不包括第i个物品的子集中，最优子集的价值是Vi-1,jo2 .在包括第i个物品的子集中（因此，j-Wi>=0）,最优子集是由该物品和前i-1个物品中能够放进承重量为j-Wi的背包的最优子集组成。这种最优子集的总价值等于vi+Vi-1,j-wi.因此，在前i个物品中最优解的总价值等于这两个价值中的较大值。当然，如果第i个物品不能放进背包，从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值

15、。这个结果导致了下面这个递推式：Vi,j=maxVi-1,j,vi+Vi-1,j-wi,j-wi>=0或者Vi,j=Vi-1,j,j-wi<0。我们可以很容易的正阳定义初始条件：当j>=0时，V0,j=0;当i>=0时，Vi,0=0。我们的目标是求Vn,W,即n个给定物品中能够放进承重量为W的背包的子集的最大总价值，以及最优子集本身。2.2.2 分支界限法：分支界限法主要是按任意方式建立如下次序：Vi/WiWv2/w2>-Wvn/wQ计算上界ub的一个简单方法是，把已经选择物品的总价值v,加上背包的剩余承重量W-w与剩下物品的最佳单位回报知Jwi+i的积：ub=v

16、+(W-w)(vL+1/wi+1)然后根据分支界限法的基本思想即可求出该0/1背包问题的最优解了。2.3 详细设计本次试验程序主要用到两个算法，分别是动态规划算法和分支界限算法，其背包问题模块流程图如下：图1背包问题模块流程图背包问题程序流程图大致如下:图2背包问题程序流程图该图很直观的描述了整个程序操作过程。2.4算法编码实现动态规划法：#include<iostream>usingnamespacestd;classbeibao(private:intW;/W为背包的承重量intn;/n为物品的数量intc20100;intw20;intv20;intx20;public:vo

17、idinput();voidsuanfa();int*display();voidbeibao:input()/由键盘输入的数据程序(cout<<"请输入背包容量W="；cin>>W;cout<<endl;cout<<"请输入物品个数n="cin>>n;cout<<endl;cout<<"请依次输入物品重量wi="for(inti=1;i<=n;i+)cin>>wi;cout<<endl;cout<<"

18、;请依次输入物品价值vi="for(intm=1;m<=n;m+)cin>>vm;cout<<endl;voidbeibao:suanfa()/动态规划算法for(intf=0;f<=W;f+)c0f=0；for(inti=1;i<=n;i+)ci0=0;for(intt=1;t<=W;t+)if(wi<=t)if(vi+ci-1t-wi>ci-1t)cit=vi+ci-1t-wi;elsecit=ci-1t;elsecit=ci-1t;)int*beibao:display()/由程序运行后输出最后结果的程序cout<

19、;<”数组ci,j为："<<endl;for(intl=0;l<=n;l+)for(intj=1;j<=W;j+)if(clj<10)cout<<clj<<""elsecout<<clj<<""if(j=W)cout<<endl;)ints=W;for(inti=n;i>1;i-)(if(cis=ci-1s)xi=0;else(xi=1;s=s-wi;)xi=c1s>0?1:0;cout<<"背包最大可容纳价值：&q

20、uot;<<cnW<<endl;returnx;)voidmain()(int*a;beibaob;b.input();b.suanfa();a=b.display();for(intk=1;k<=20;k+)if(ak=1)cout<<"物品"<<k<<”被装进背包。"<<endl;)分支界限法：#include<stdio.h>#include<malloc.h>#defineMaxSize100/最多节点数typedefstructQNode(floatwe

21、ight;floatvalue;intceng;structQNode*parent;boolleftChild;QNode,*qnode;/存放每个节点typedefstruct(qnodeQMaxSize;intfront,rear;SqQueue;/存放节点的队列SqQueuesq;floatbestv=0;/最优解intn=0;/实际物品数floatwMaxSize;/物品的重量floatvMaxSize;/物品的价值intbestxMaxSize;/存放最优解qnodebestE;voidInitQueue(SqQueue&sq)/队列初始化(sq.front=1;sq.re

22、ar=1;boolQueueEmpty(SqQueuesq)/队列是否为空(if(sq.front=sq.rear)returntrue;elsereturnfalse;)voidEnQueue(SqQueue&sq,qnodeb)/入队if(sq.front=(sq.rear+1)%MaxSize)printf("队列已满!");return;)sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;)qnodeDeQueue(SqQueue&sq)/出队qnodee;if(sq.front=sq.rear)printf(&qu

23、ot;队列已空!");return0;)e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;returne;)voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild)qnodeb;if(i=n)/可行叶子节点if(vt=bestv)(bestE=parent;bestxn=(leftchild)?1:0;)return;)b=(qnode)malloc(sizeof(QNode);/非叶子节点b->weight=wt;b->value=vt;b->ceng=i;b

24、->parent=parent;b->leftChild=leftchild;EnQueue(sq,b);)voidmaxLoading(floatw,floatv,intc)(floatwt=0;floatvt=0;inti=1;/当前的扩展节点所在的层floatew=0;/扩展节点所相应的当前载重量floatev=0;/扩展节点所相应的价值qnodee=NULL;qnodet=NULL;InitQueue(sq);EnQueue(sq,t);/空标志进队列while(!QueueEmpty(sq)(wt=ew+wi;vt=ev+vi;if(wt<=c)(if(vt>

25、bestv)bestv=vt;EnQueue1(wt,vt,i,e,true);/左儿子节点进队)EnQueue1(ew,ev,i,e,false);/右儿子总是可行e=DeQueue(sq);/取下一扩展节点if(e=NULL)(if(QueueEmpty(sq)break;EnQueue(sq,NULL);/同层节点尾部标识e=DeQueue(sq);/取下一扩展节点i+;)ew=e->weight;/更新当前扩展节点的值ev=e->value;)printf("最优取值法为：n");for(intj=n-1;j>0;j-)/构造最优解(bestxj=

26、(bestE->leftChild?1:0);bestE=bestE->parent;)for(intk=1;k<=n;k+)(if(bestxk=1)printf("n物品d:重量:.1f,价值:%.1fn",k,wk,vk);)printf("n");printf("最有价值为:%.1fnn",bestv);)voidmain()(intc;floatewvMaxSize;printf("/0-1背包问题分支界限法/八nn");printf("请输入物品的数量:n");sc

27、anf("%d",&n);printf("请输入背包的最大承重量:n");scanf("%d",&c);printf("n请输入物品的重量和单位重量价值:nn");for(inti=1;i<=n;i+)(printf("物品d:",i);scanf("%f%f',&wi,&ewvi);vi=wi*ewvi;printf("n");)maxLoading(w,v,c);)3 .程序运行平台WindowsXP和Microso

28、ftVisualC+6.0。具体操作如下：点击MicrosoftVisualC+6.0图标，进入C+钟面，点击菜单栏里的“文件”，选择新建，进而选择工程里的“Win32ConsoleApplication"，输入名称和存储路径并确定；然后再点击菜单栏里的“文件”选择新建，进而选择文件里的“C+SourceFile”，输入文件名后按确定。创建源文件后，在里面输入程序的内容，先点击“Comfile”，然后点击“Build"，无错误后，最后点击“BuildExecute"，进入程序界面。4 .系统测试4.1 测试数据背包承重量：10物品个数：5物品重量：25746物品价

29、值：221004940544.2 测试结果物品最优解：物品2和物品4被放入背包。背包可容最大价值为：1404.3 程序运行结果动态规划算法运行结果如下：下图的结果与测试结果是相同的，所以动态规划算法所求0/1背包问题是可以运用的，所以该程序是完整的、正确的。京>ociimentsandSettingsAdniint5trator£iDebug情输入背包容量请输入物品个数k5请依次输入物品重量或打=25746请依次输入物品价值5灯=22100494054数组cd.最为：30003000003222222222222!22222232222221001001221221221223

30、222222100100122122122122B222240100100122122140140a2222401001BB背包最大可寄的价值：122140122140140pressanykeytocontinue分支界限法运行结果如下:tA七VkKUineii匕andSetting*Administrator溟面曲支界限法、Debug份支产产产产产产产/产/用背包(可题分支界巾艮?去，/请输入物品的数量二片输入背包的最大承重量;10请输入物品的重量和单位重量价值二物品，211物品2鸣20物品3177物品如410物品5遥9最优期值法为：物品2:重量;5.瓦价值目目,目物品条重量t4.乩价值:

31、4。.附最有价值为：1翎.且PressaGS及白沙toconitlnue图4上图运行出来的结果和测试结果是相同的。但是其中必须要先转换，就是把物品价值转换成单位重量价值。用物品价值除以物品的重量就等于物品单位重量价值，然后再由键盘输入，最后运行出来结果如上图。4.4 算法的时间复杂度分析。动态规划算法的时间复杂度为o(min(nC,2An),其中n为物体的个数,C为背包负重。精确算法的优点是当问题规模较小时一定可以求得最优解，缺点是当问题规模较大时因计算量太大而无法实现。所以一些学者提出了各种近似算法来解决精确算法求解背包问题时的时间复杂性和空间复杂性难题。分支界限算法的时间复杂度是0(2&q

32、uot;),我们可以做一些简单的优化。由于本题中的所有物品的体积均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单的以空间换时间。结论本次课程设计，我学到了很多。首先本次课程设计主要是对数据结构所学知识进行实践应用，不仅把数据结构的知识巩固了，还把知识运用到了实践当中，使我在各方面的能力都得到了提高。这次实验我用的是动态规划法和分支界限法解决0/1背包问题。在做这次课程设计的时候，我相继遇到了很多问题，自己对知识的不熟悉以及更多的不足之处也相继的暴露了出来。但是因为

33、努力去做好这个课程设计，所以有针对性的去查漏补缺，不断的弥补自己的缺陷，从中我学到的东西更深刻、更透彻、更丰富，对算法也有了更加进一步的理解。在这次的上机实践过程中，我对C+邮言有了更深的认识和了解，其中动态规划法直接是在C+抨台用C+邮言编写的，分支界限法是在C+W台用C语言编写的。同时我知道，要想把C+惇好，主要是在实践当中，通过实践不断的发现自己的不足，并且不断的改正，才能熟练的掌握它。当然，在上机的同时也必须要有一定的C+!论知识，只有这样，才能做到理论与实践相促进，才能同时提高。同时，我还认识到了一个非常重要的问题，那就是算法的重要性。在做程序的时候，我们必须要了解一个算法。在做这个

34、背包问题的时候，最开始我都不知道到底要用什么方法，但是看了算法设计与分析后，我发现了解决背包问题用动态规划法和分支界限法很简单，因为这两个算法给我从不同的角度去解决一个问题提供了很好的结构和算法来解决现实中比较难的程序。同时，她还能帮助我们减少程序在时间和空间上的花费。在许多与编程有关的地方都要用到算法设计的知识。最后，在上机实验中，我发现了我自己在基础知识方面还有待提高。很多算法都不能直接准确的写出来，都必须翻看书籍，照着书上来完成，有的时候还会因为空间分配等问题造成最后程序错误，但是经过多次的实践，再把用笔算的结果进行比对，再慢慢一遍遍看程序，最后把程序改正确了。这种坚持不懈的习惯使我在程

35、序设计中能做到查漏补缺，弥补自己的不足，更使我明白，不管学什么，都应该在动脑的同时动手去做。致谢本次课程设计能够顺利完成，首先我要感谢的是我的授课老师黄襄念老师，是他一直鼓励和教导我们，给我们讲解知识，让我们在课堂上能够很好的理解知识，才能在实践中有好的运用。其次我还要感谢我的指导老师谢春芝老师，是他在上机的时候对我孜孜不倦的教导，让我有信心坚持努力的做下去，同时给了我们做课程设计的思想和基础。在谢老师的引导、启发和鼓励下，我才能够顺利的完成这个课程设计。最后要感谢的是我们寝室的同学，是她们在我不懂的时候，慢慢的帮助我，给我讲解，使我在整个过程中有坚强的后盾。这些都比在书上学到的管用的多，因为

36、在她们的帮助下，我学的东西更多更深刻，她们的帮助让我受益匪浅。所以，要再次感谢那些帮助过我的老师和同学。参考文献1严蔚敏吴伟民著.数据结构（C语言版）（第三版）.北京：清华大学出版社2007.42谭浩强著.C程序设计（第三版）.北京：清华大学出版社；2006.93AnanyLevitin著.潘彦译算法设计与分析基础（第二版）.北京：清华大学出版社；2010.14美S巴斯著.计算机算法：设计和分析引论.朱洪等译上海：复旦大学出版社；1985.1附录一、动态规划法#include<iostream>usingnamespacestd;classbeibaoprivate:intW;in

37、tn;intc20100;intw20;intv20;intx20;public:voidinput();voidsuanfa();int*display(););voidbeibao:input()cout<<"请输入背包容量W="cin>>W;cout<<endl;cout<<"请输入物品个数n="cin>>n;cout<<endl;cout<<"请依次输入物品重量wi="for(inti=1;i<=n;i+)cin>>wi;co

38、ut<<endl;cout<<"请依次输入物品价值vi="for(intm=1;m<=n;m+)cin>>vm;cout<<endl;)voidbeibao:suanfa()for(intf=0;f<=W;f+)c0f=0;for(inti=1;i<=n;i+)ci0=0;for(intt=1;t<=W;t+)if(wi<=t)if(vi+ci-1t-wi>ci-1t)cit=vi+ci-1t-wi;elsecit=ci-1t;elsecit=ci-1t;int*beibao二display

39、。cout<<”数组ci,j为："<<endl;for(intl=0;l<=n;l+)if(clj<10)cout<<clj<<for(intj=1;j<=W;j+)(elsecout<<clj<<""if(j=W)cout<<endl;ints=W;for(inti=n;i>1;i-)(if(cis=ci-1s)xi=0;else(xi=1;s=s-wi;xi=c1s>0?1:0;cout<<"背包最大可容纳价值："&

40、lt;<cnW<<endl;returnx;voidmain()(int*a;beibaob;b.input();b.suanfa();a=b.display();for(intk=1;k<=20;k+)if(ak=1)cout<<"物品"<<k<<"被装进背包。"<<endl;乙、分支界限法#include<stdio.h>#include<malloc.h>#defineMaxSize100/最多节点数typedefstructQNode(floatwei

41、ght;floatvalue;intceng;structQNode*parent;boolleftChild;QNode,*qnode;/存放每个节点typedefstruct(qnodeQMaxSize;intfront,rear;SqQueue;/存放节点的队列SqQueuesq;floatbestv=0;/最优解intn=0;/实际物品数floatwMaxSize;物品的重量floatvMaxSize;物品的价值intbestxMaxSize;/存放最优解qnodebestE;voidInitQueue(SqQueue&sq)sq.front=1;sq.rear=1;)bool

42、QueueEmpty(SqQueuesq)if(sq.front=sq.rear)returntrue;elsereturnfalse;/队列初始化/队列是否为空/非叶子节点voidEnQueue(SqQueue&sq,qnodeb)/入队if(sq.front=(sq.rear+1)%MaxSize)pprintf("队列已满!");return;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;qnodeDeQueue(SqQueue&sq)/出队qnodee;if(sq.front=sq.rear)printf("队列已空!");return0;e=sq.Qsq.front;sq.fro