1、0,1背包问题的应用

1、1厉#2罟数学与计算机学院课程设计说明书课程名 称：算法设计与分析-课程设计课程代码：7106620题目： 0/1背包问题的应用年级/专业/班学生姓名：学 号开始时间:2010年 12 月 27日 完成时间:2011年 01 月 07日课程设计成绩:学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年 月 日目录 TOC o 1-5 h z 摘要1 HYPERLINK l bookmark10 o Current Document 1引言2 HYPERLINK l bookmark12 o Current Document 1.1问

2、题的提出2 HYPERLINK l bookmark14 o Current Document 1.2背包问题的研究现状2 HYPERLINK l bookmark16 o Current Document 1.3求解0-1背包问题常见方法 3 HYPERLINK l bookmark18 o Current Document 1.4算法设计与分析的地位3 HYPERLINK l bookmark20 o Current Document 1.5动态规划的基本思想3 HYPERLINK l bookmark22 o Current Document 1.6分支界限法的基本思想4 HYPERLI

3、NK l bookmark24 o Current Document 1.7任务与分析4 HYPERLINK l bookmark26 o Current Document 2设计方案4 HYPERLINK l bookmark28 o Current Document 2.1问题描述42.2算法描述和设计42.2.1动态规划法42.2.2分支界限法5 HYPERLINK l bookmark32 o Current Document 2.3详细设计5 HYPERLINK l bookmark34 o Current Document 2.4算法编码实现63程序运行平台 14 HYPERLIN

4、K l bookmark38 o Current Document 4系统测试14 HYPERLINK l bookmark40 o Current Document 4.1测试数据15 HYPERLINK l bookmark42 o Current Document 4.2测试结果15 HYPERLINK l bookmark44 o Current Document 4.3程序运行结果15 HYPERLINK l bookmark50 o Current Document 4.4算法的时间复杂度分析 16 HYPERLINK l bookmark52 o Current Document

5、 结论17 HYPERLINK l bookmark54 o Current Document 致谢18 HYPERLINK l bookmark56 o Current Document 参考文献190/1背包问题的应用摘要针对一类难解的0/1背包问题，揭示了该类问题和子集和数问题的相似性，及该类问 题特有的属性；描述了最大价值的获得与物品集中元素的组合相关性。在价值密度比贪心 策略基础上设计了一个搜索算法。实验表明，在多项式时间复杂度内得到的解的质量优于 目前最好算法的结果。本文算法的最优解与物品集中元素的重量和价值参数的大小分布无 关，而只与元素的重量及背包零头的组合相关，因而具有相当的

6、竞争力。0/1背包问题是实际当中经常遇到的一类经典NP hard组合优化问题之一。本文分 别从贪心方法、动态规划、回溯法、分支限界法，遗传算法这五种算法设計方法入手，概 述了各种设计方法的基本原理，提出了求解0/1背包问题的算法思想，并对算法进行分析， 提出了改进方法。关键词：0/1背包问题；动态规划；分支限界法1引言对于计算机科学来说，算法的概念是至关重要的。在一个大型软件系统的开发中，设 计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此， 算法分析与设计成为计算科学的核心问题之一，也是信息与计算科学专业本科及研究 生的一门重要的专业基础课。算法分析与设计是计算机

7、软件开发人员必修课，软件的效率 和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计 与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析 算法的“好”与“坏”，怎样设计算法，并以广泛用于计算机科学中的算法的思维方式， 改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课 课程的知识。1.1问题的提出它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品， 重量各不同。此人通过秘密的选择一部分物品并将它们放到背包中来加密消息。背包中的 物品中重量是公开的，所有可能的物品也是公开的，但

8、背包中的物品时保密的。附加一定 的限制条件，给出重量，而要列出可能的物品，在计算机上是不可实现的。背包问题是熟 知的不可计算问题，背包体制以其加密，解密速度的快而其人注目。在解决大量的复杂组 合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题 来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是经典的应 用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中叶起着重要 的作用。然而当问题的规模较大时，得到最优解是极其困难的。但是，大多数一次背包体 制均被破译了，因此现在很少人使用它。背包问题是一种组合优化的NP完全问题。问题可以描述为

9、：在杂货店中有n种不同 的货物。现将货物装车，规定从每种货物中最多只能拿一件，车子的容量为W，物品i需 要占用Wi的空间，价值为Vi。现要求设计算法和程序使车中装载的物品价值最大。当然， 所装货物不能超过车的容量，且同一种物品不得拿走多件。1.2背包问题的研究现状Dantzing在20世纪50年代首先进行了开创性的研究，利用贪婪算法求得了 0-1背 包问题最优解的上界。1974年，horowitz和salmi利用分支界限法解答背包问题，并提 出了背包问题的可分性，指出了求解该问题的一条新途径。随后，balas和zemel提出了 背包问题的“核”思想，使背包问题的研究获得了较大进展。上世纪九十年

10、代以后，随着 生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现， 例如遗传算法已经在0/1背包问题上得到较好的应用，蚂蚁算法等仿生算法也在组合优化 问题中得到了很好的应用。1.3求解0-1背包问题常见方法传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划 法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等， 由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题成 为重点。本次课程设计，我们主要用动态规划法和分支界限法来求解该背包问题。1.4算法设计与分析的地位算法设计与分析在计算机科学中是一门综合

11、性的专业基础课。算法的研究不仅涉及 到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软 件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器 中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更 为方便。因此，可以认为算法设计与分析是介于数学、计算机硬件和计算机软件三者之间 的一门核心课程。在计算机科学中，算法设计与分析不仅是一般程序设计的基础，而且是 设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。1.5动态规划的基本思想动态规划法是上世纪50年代Richard Bellman创建

12、的解决多阶段决策过程最优化的 一种数学方法，即把多阶段决策问题变换为一系列相互联系单阶段问题，然后逐个加以解 决。它的特点是解决多阶段、离散性问题。动态规划算法的基本思想是把原问题分解成一 系列子问题，然后从这些子问题中求出原问题的解。对一个负重能力为C的背包，如果选 择装入第i种物品，那么原背包问题就转化为负重能力为C-ci的子背包问题。动态规划 算法是一种经典的背包问题求解算法，其原理简单，算法思路清晰，易于实现。动态规划 算法虽然高效，但是对于规模较大的问题它不是一个理想的算法，主要原因就是它的维数 障碍，即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。动 态规划算

13、法的时间复杂度为o（min（nC，2n）,其中n为物体的个数,C为背包负重。精确算法的优点是当问题规模较小时一定可以求得最优解，缺点是当问题规模较大 时因计算量太大而无法实现。所以一些学者提出了各种近似算法来解决精确算法求解背 包问题时的时间复杂性和空间复杂性难题。1.6分支界限法的基本思想用分支界限算法求解背包问题具有相当不寻常的特征。一般来说，一棵状态空间树的 中间节点并不能确定问题的查找空间中的一个点，因为解得某些分量还未明确。然而，对 于背包问题来说，树的每一个节点都可以代表给定物品的一个子集。在生成了树中的每一 个新节点之后，我们可以利用这个事实，来更新目前为止的最佳子集信息。1.7

14、任务与分析1给出多种求解算法，如动态规划法、贪婪法。编程实现所给算法。对所写算法给出时间空间复杂性分析。2设计方案2.1问题描述在杂货店中有n种不同的货物。现将货物装车，规定从每种货物中最多只能拿一件, 车子的容量为W，物品i需要占用Wi的空间，价值为Vi。现要求设计算法和程序使车中 装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。 2.2算法描述和设计本实验主要是运用动态规划法和分支界限法解0/1背包问题。算法分析如下：2.2.1动态规划法：我们可以把前i个物品中能够放进承重量为j的背包中的子集分成两个类别:包括第 i个物品的子集和不包括第i个物品的子集。有下结

15、论：根据定义，在不包括第i个物品的子集中，最优子集的价值是Vi-1,j。在包括第i个物品的子集中（因此，j-Wi=0）,最优子集是由该物品和前i-1个物品 中能够放进承重量为j-Wi的背包的最优子集组成。这种最优子集的总价值等于vi+Vil,jwi.因此，在前i个物品中最优解的总价值等于这两个价值中的较大值。当然，如果第i个物 品不能放进背包，从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的 最优子集的总价值。这个结果导致了下面这个递推式：Vi,j二maxVi1,j,vi+Vi1,jwi,jwi=0 或者Vi,j=Vi-1,j,j-wi=0 时，V0,j=0;当 i=0 时，V

16、i,0=0。我们的目标是求Vn,W，即n个给定物品中能够放进承重量为W的背包的子集的最大总 价值，以及最优子集本身。2.2.2分支界限法：分支界限法主要是按任意方式建立如下次序：计算上界ub的一个简单方法是，把已经选择物品的总价值v,加上背包的剩余承重量W-w与剩下物品的最佳单位回报的积：ub = v4(W-w)(vu /%然后根据分支界限法的基本思想即可求出该0/1背包问题的最优解了。2.3详细设计本次试验程序主要用到两个算法，分别是动态规划算法和分支界限算法，其背包问题 模块流程图如下：图1背包问题模块流程图背包问题程序流程图大致如下:图2背包问题程序流程图 该图很直观的描述了整个程序操作

17、过程。2.4算法编码实现动态规划法：#include using namespace std;class beibaoprivate:int W;/W为背包的承重量int n;/n为物品的数量int c20100;int w20;int v20;int x20;public:void inp ut();void suanfa();int* display。；;void beibao:inpu t()/由键盘输入的数据程序coutW;coutendl;coutn;coutendl;coutwi;coutendl;cout请依次输入物品价值vi=;for(int m=1;mvm;coutendl;

18、void beibao:suanfa()/动态规划算法for(int f=0;fci1 t)ci t二 vi+ci1 twi;elseci t=ci1 t;elseci t二ci1 t;int* beibao:display()/由程序运行后输出最后结果的程序cout数组 ci,j为：endl;for(int l=0;l二n;l+)for(int j=1;j=W;j+)if(clj10)cou t clj;else cout clj if(j=W)cout1;i-)if(cis=ci-1s) xi=0;elsexi = 1; s=s-wi; xi=c1s0?1:0;cou t背包最大可容纳价值

19、：cnWendl; return x; void main()int *a;beibao b;b.inp ut();b.suanfa();a二b.displayO;for(int k=1;k=20;k+)if(ak=1)cou t物品 k被装进背包 endl;分支界限法：#include #include#define MaxSize 100/最多节点数typedef struet QNodefloat weight;float value;int eeng;struet QNode*parent;bool leftChild;QNode, *qnode;/存放每个节点typedef stru

20、etqnode QMaxSize; int front ,rear;SqQueue;/存放节点的队列SqQueue sq;floa t bes tv=0; /最优解 int n=0;/实际物品数floa t wMaxSize; /物品的重量 floa t vMaxSize; /物品的价值 int bes txMaxSize; /存放最优解 qnode bestE;void Ini tQueue(SqQueue&sq) /队列初始化sq.fro nt =1;sq.rear =1;bool QueueEmp ty(SqQueue sq) /队列是否为空 if(sq.fro nt二二sq.rear)

21、return true;elsereturn false;void EnQueue(SqQueue&sq,qnode b) /入队if(sq.fro nt二=(sq.rear+1)%MaxSize)prin tf(队列已满!);return;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;qnode DeQueue(SqQueue&sq)/ 出队qnode e;if(sq.fro nt二二sq.rear)prin tf(队列已空!);return 0;e二sq.Qsq.fro nt;sq.fro nt二(sq.fro nt+1)%MaxSize;return

22、 e;void EnQueue1(floa t wt,f loa t vt,int i,QNode *pare nt ,bool lef tchild)qnode b;if(i=n) /可行叶子节点 if(vt二二bes tv)bestE二parent;bes txn = (lef tchild)?1:0; return;b=(qnode)malloc(sizeof(QNode); /非叶子节点 bweight二wt;b-value=vt;bceng=i;bparent二parent;bleftChild=leftchild;EnQueue(sq,b);void maxLoading(floa

23、 t w,floa t v,int c)float wt=0;float vt=0;int i=1;/当前的扩展节点所在的层float ew=0;/扩展节点所相应的当前载重量float ev=0;/扩展节点所相应的价值qnode e二NULL;qnode t二NULL;InitQueue(sq);EnQueue(sq, t);/空标志进队列while(!QueueEmpty (sq)wt二ew+wi;vt二ev+vi;if(w tbestv)bestv二vt;EnQueue1(w t,v t,i,e, true); /左儿子节点进队EnQueue1(ew,ev,i,e,false); /右儿子

24、总是可行e二DeQueue(sq); /取下一扩展节点if(e=NULL)if(QueueEmpty(sq) break;EnQueue(sq,NULL); /同层节点尾部标识e二DeQueue(sq); /取下一扩展节点i+;ew=e-weigh t; /更新当前扩展节点的值ev=e-value;prin tf(最优取值法为:n);for(int j二n-1;j0;j) /构造最优解bestxj=(bestE-leftChild?1:0);bestE二bestEparent;for(int k=1;k=n;k+)if(bes txk=1)printf(n 物品%d:重量:%.1f,价值:%.

25、1fn,k,wk,vk);pri ntf (n);prin tf（最有价值为:%.1fnn,bes tv）;void main（）int c;float ewvMaxSize;prin tf（/0-1 背包问题分支界限法/nn）;prin tf（请输入物品的数量:n）；scanf（%d，&n）;prin tf（请输入背包的最大承重量:n）；scanf（%d，& c）;printf（n请输入物品的重量和单位重量价值:nn）；for（int i=1;i二n;i+）prin tf（ 物品 %d:,i）;scanf（%f%f ，& wi ，& ewvi）;vi=w i* ewvi;pri ntf （n

26、）；maxLoading（w,v,c）;程序运彳丁平台Windows XP 和 Microsoft Visual C+ 6.0。具体操作如下：点击Microsoft Visual C+ 6.0图标，进入C+界面，点击菜单栏 里的“文件”选择新建，进而选择工程里的“Win32 Console Application”输入名称 和存储路径并确定；然后再点击菜单栏里的“文件”选择新建，进而选择文件里的“C+ Source File”输入文件名后按确定。创建源文件后，在里面输入程序的内容，先点击 “Comfile”，然后点击Build”无错误后，最后点击BuildExecute”进入程序界面。系统测试

27、4.1测试数据背包承重量：10 物品个数：5物品重量：2 5 7 4 6物品价值：22 100 49 40 544.2测试结果物品最优解：物品2和物品4被放入背包。背包可容最大价值为：1404.3程序运行结果动态规划算法运行结果如下：下图的结果与测试结果是相同的，所以动态规划算法所求0/1背包问题是可以运用的，所以该程序是完整的、正确的。p,C：XDocundents rud SettingsAdniinistrator面动态规划袪塀 请输入背包容量帖価请输入物品个数n巧请恢次输入物品重量=2 5 7 4 6猜依次输入物品价值=22 100 49 40 54Q22222240400 0 0 0

28、22 22 22 22100 100 22100 100 122106 160 122106 160 122擞组ci,j为：Q Q22 22122 122 122122 122 122122 140 140122 140 140140物品理叢葵进背包。Pressto continue分支界限法运行结果如下:图4上图运行出来的结果和测试结果是相同的。但是其中必须要先转换，就是把物品价值 转换成单位重量价值。用物品价值除以物品的重量就等于物品单位重量价值，然后再由键 盘输入，最后运行出来结果如上图。4.4算法的时间复杂度分析。动态规划算法的时间复杂度为o(min(nC, 2n),其中n为物体的个数

29、,C为背包 负重。精确算法的优点是当问题规模较小时一定可以求得最优解，缺点是当问题规模较 大时因计算量太大而无法实现。所以一些学者提出了各种近似算法来解决精确算法求解 背包问题时的时间复杂性和空间复杂性难题。分支界限算法的时间复杂度是O(2b),我们可以做一些简单的优化。由于本题中的 所有物品的体积均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重 复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重 复计算的话，速度就会提高很多。这是简单的以空间换时间。结论本次课程设计，我学到了很多。首先本次课程设计主要是对数据结构所学知识进行实 践应用，不仅把数据结

30、构的知识巩固了，还把知识运用到了实践当中，使我在各方面的能 力都得到了提高。这次实验我用的是动态规划法和分支界限法解决0/1背包问题。在做这 次课程设计的时候，我相继遇到了很多问题，自己对知识的不熟悉以及更多的不足之处也 相继的暴露了出来。但是因为努力去做好这个课程设计，所以有针对性的去查漏补缺，不 断的弥补自己的缺陷，从中我学到的东西更深刻、更透彻、更丰富，对算法也有了更加进 一步的理解。在这次的上机实践过程中，我对C+语言有了更深的认识和了解，其中动态规划法直 接是在C+平台用C+语言编写的，分支界限法是在C+平台用C语言编写的。同时我知 道，要想把C+学好，主要是在实践当中，通过实践不断

31、的发现自己的不足，并且不断的 改正，才能熟练的掌握它。当然，在上机的同时也必须要有一定的C+理论知识，只有这 样，才能做到理论与实践相促进，才能同时提高。同时，我还认识到了一个非常重要的问题，那就是算法的重要性。在做程序的时候， 我们必须要了解一个算法。在做这个背包问题的时候，最开始我都不知道到底要用什么方 法，但是看了算法设计与分析后，我发现了解决背包问题用动态规划法和分支界限法很简 单，因为这两个算法给我从不同的角度去解决一个问题提供了很好的结构和算法来解决现 实中比较难的程序。同时，她还能帮助我们减少程序在时间和空间上的花费。在许多与编 程有关的地方都要用到算法设计的知识。最后，在上机实

32、验中，我发现了我自己在基础知识方面还有待提高。很多算法都不能 直接准确的写出来，都必须翻看书籍，照着书上来完成，有的时候还会因为空间分配等问 题造成最后程序错误，但是经过多次的实践，再把用笔算的结果进行比对，再慢慢一遍遍 看程序，最后把程序改正确了。这种坚持不懈的习惯使我在程序设计中能做到查漏补缺， 弥补自己的不足，更使我明白，不管学什么，都应该在动脑的同时动手去做。致谢本次课程设计能够顺利完成，首先我要感谢的是我的授课老师黄襄念老师，是他一直 鼓励和教导我们，给我们讲解知识，让我们在课堂上能够很好的理解知识，才能在实践中 有好的运用。其次我还要感谢我的指导老师谢春芝老师，是他在上机的时候对我

33、孜孜不倦 的教导，让我有信心坚持努力的做下去，同时给了我们做课程设计的思想和基础。在谢老 师的引导、启发和鼓励下，我才能够顺利的完成这个课程设计。最后要感谢的是我们寝室 的同学，是她们在我不懂的时候，慢慢的帮助我，给我讲解，使我在整个过程中有坚强的 后盾。这些都比在书上学到的管用的多，因为在她们的帮助下，我学的东西更多更深刻， 她们的帮助让我受益匪浅。所以，要再次感谢那些帮助过我的老师和同学。参考文献严蔚敏 吴伟民著.数据结构（C语言版）（第三版）.北京：清华大学出版社2007.4谭浩强著.C程序设计（第三版）北京：清华大学出版社；2006.9Anany Levi tin著.潘彦译 算法设计与

34、分析基础（第二版）.北京：清华大 学出版社；2010.1美S巴斯著计算机算法：设计和分析引论.朱洪等译上海：复旦大学出版 社；1985.1附录一、动态规划法#i nclude using n amespace std; class beibaoprivate:int W;int n;in t c20100;int w20; in t v20;int x20; public:void in put();void sua nfa();int* display();void beibao: in put()cout W;coute ndl;coutn;coute ndl;cout请依次输入物品重量w

35、i=; for(i nt i=1;i wi;coute ndl;cout请依次输入物品价值vi=; for(i nt m=1;m vm;coutend ;void beibao:sua nfa()for(i nt f=0;f=W;f+) c0f=0;for(i nt i=1;i=n ;i+) ci0=0; for(i nt t=1;t=W;t+) if(wici-1t) cit=vi+ci-1t-wi; elsecit=ci-1t; elsecit=ci-1t;int* beibao:display()cout数组 ci,j为：endl;for(i nt l=0;l=n ;l+) for(i

36、nt j=1;j=W;j+) if(clj10) coutcljelse coutclj; if(j=W)cout1;i-) if(cis=ci-1s) xi=O; elsexi=1; s=s-wi;xi=c1s0?1:0;cout背包最大可容纳价值：cnWendl; return x;void mai n()int *a; beibao b;b.i nput();b.sua nfa();a=b.display();for(i nt k=1;k=20;k+) if(ak=1)cout物品k被装进背包。endl; 二、分支界限法 #i nclude #i nclude#defi ne MaxSi

37、ze 100最多节点数typedef struct QNodefloat weight;float value;int ceng;struct QNode*pare nt;bool leftChild;QNode,*q no de;存放每个节点typedef structqnode QMaxSize;int fron t,rear;SqQueue;存放节点的队列SqQueue sq;float bestv=0; 最优解int n=0; 实际物品数float wMaxSize; /物品的重量void Ini tQueue(SqQueue&sq) 队列初始化float vMaxSize; 物品的价

38、值 int bestxMaxSize; 存放最优解 qnode bestE;sq.fr ont =1;sq.rear =1;bool QueueEmpty(SqQueue sq) 队列是否为空 if(sq.fro nt=sq.rear)elsereturn false;void En Queue(SqQueue&sq,qnode b) 入队 if(sq.fro nt=(sq.rear+1)%MaxSize)printf(队列已满!); return; sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;return true;qnode DeQueue(SqQueue&sq) 出队qnode e;if(sq.fro nt=sq.rear) 宀 printf(队列已空!)； return 0; e=sq.Qsq.f