背包问题的算法研究与实现本科.doc

《背包问题的算法研究与实现本科.doc》由会员分享，可在线阅读，更多相关《背包问题的算法研究与实现本科.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流背包问题的算法研究与实现本科.精品文档.华中师范大学汉口分校本 科 毕 业 论 文0-1背包问题的算法研究与实现院 系：信息科学技术学院 专 业：计算机科学与技术 年 级： 2005级 学 生： 刘念 学 号： 2005911032 指导老师： 宾云峰、杨健 华中师范大学汉口分校学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师指导下独立进行研究工作所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。学位论文作者签名： 日期： 年 月

2、日学位论文版权使用授权书本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密 ，在_年解密后适用本授权书。2、不保密 。（请在以上相应方框内打“”）学位论文作者签名： 日期： 年 月 日导师签名： 日期： 年 月 日目 录内容摘要1关 键 词1ABSTRACT2KEY WORDS21 绪论31.1问题的提出及研究意义31.2 0-1背包问

3、题的算法研究的分析31.3课题的主要研究内容42 0-1背包问题的实现52.1 0-1背包问题在动态规划中的实现52.2 0-1背包问题在回溯法中的实现82.3 0-1背包问题在分枝-限界法中的实现122.4 0-1背包问题在遗传算法中的实现163 解0-1背包问题的算法比较与分析204总结与展望22参考文献23致 谢25内容摘要：背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题

4、具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用动态规划法，回溯法，分枝-限界法，遗传算法四种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结四种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。关 键 词：0-1

5、背包 动态规划 回溯法 分枝-限界法 遗传算法Abstract： Knapsack problem is a typical NP-C problem as well as algorithm design and analysis of the classical problems in the common field of operations research. It is very important to study the solution of the problem, whether in theory or in practice. After some research,

6、 a lot of classical methods solving this problem have been come up with ,and the exploration of this issue and applied research has been ongoing. Under the guidance of advanced theory, there are distinctive features such as scientific, efficient, economic, flexible and convenient features in solving

7、 the 0-1 knapsack problem .So to solve the knapsack problem, the first premise is to design a good algorithm.To seek the solution of knapsack problem, it is necessary to design algorithms using dynamic programming at first. In this paper, four methods such as dynamic programming, backtracking, branc

8、h - Bound method and genetic algorithm respectively aiming at knapsack problem ,0-1 knapsack problem and a simple 0-1 knapsack problem carry out the algorithm design and analysis of time complexity, and give the specific algorithm design and implementation of the process.And descript detailedly the

9、basic idea of algorithm by using specific examples in solving the issue with different ways .And then aiming at solving the 0-1 knapsack problem , compare four algorithms in detail and summarize the advantages and disadvantages of realization of four methods and reach a conclusion.How to apply the k

10、napsack problem into the practical, and to design targeted for the practical algorithms of solving 0-1 Knapsack Problem and to solve the practical problems very well, is an area of computer workers constantly thinking and study. Key words：0-1 knapsack problem dynamic programmi backtracking branch -

11、Bound method genetic algorithm1 绪论1.1问题的提出及研究意义0-1背包问题是计算机科学中的一个非常经典的优化问题。也是被证明了的NP难度问题。它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此

12、现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法。多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。1.2 0-1背包问题的算法研究的分析 0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现

13、，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。0-1背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。它包含了背包问题中设计状态、方程的最基本思想，在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属

14、于NP-C完全问题，其计算复杂度，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。1.3课题的主要研究内容1.3.1背包问题的描述背包问题是整数规划中的一类特殊问题，在现实生活中具有广泛应用。如果能提出求解此问题的有效算法，则具有很好的经济价值和决策价值。问题的一般描述是：旅行者背包登山，背包的最大承重为M，现有n个物品可供选择装入背包，第i个物品莺量为wi，价值为pi，假定物品i的一部分xi(0xi1)放人背包，获得价值为xipi，由于背包最大承重为M，要求装入物品总质量不过超过M，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大

15、值。背包问题的数学描述如下：要求找到一个n元向量(x1，x2xn)，在满足约束条件：情况下，使得目标函数，其中，1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解1。 1.3.2 0-1背包问题 0-1背包问题的提出给定n 种物品和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。 问题符号化 0-1背包问题的符

16、号化表示是，给定M0， w i 0， pi 0，1in ，要求找到一个n元0-1向量向量(x1，x2xn)， X i =0 或1 , 1in, 使得 ，而且达到最大2。2 0-1背包问题的实现2.1 0-1背包问题在动态规划中的实现2.1.1 动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求

17、解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：分析最优解的结构：最有子结构性质；建立递归方程；计算最优值；构造最优解4。动态规划算法的每一步决策都是根据前一步的状态参量来决定这一步状态参量的设置，也就是说，从初始状态到最终状态要经过多个过程，经历不同的状态，不断地根据上一步状态决定下一状态，从而形成了一个决策序列，最终将整个问题解决，这就是典型的多段决策的特性。由上面的动态规划法的介绍，可以看出0-1背包问题，是符合多段决策

18、的特点和具有重叠子问题。因此，在设计0-1背包问题解决方案时，可以将整个物品放到背包的过程，看成一个取物品的过程。 2.2.2 0-1背包问题的实现 最优子结构性质0-1背包问题具有最优子结构性质。设(y1，y2yn)是所给0-1背包问题的一个最优解，则(y2，y3yn)是下面相应子问题的一个最优解：因若不然，设(z2，z3zn)是上述问题的一个最优解，而(y2，y3yn)不是它的最优解，由此可见,且c。因此c这说明(y1，z2zn)是所给0-1背包问题的一个更优解，从而(y1，y2yn)不是所给0-1背包问题的最优解。此为矛盾1。 递归关系设所给0-1背包问题的子问题 的最优值为m(i,j)

19、，即m(i,j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下： 算法描述基于以上讨论，当wi(1in)为正整数时，用二维数组m来存储m(i,j)的相应值，可设计解0-1背包问题的动态规划算法Knapsack入下：templatevoid Knapsack(Type v,int w,int c,int n,Type* * m) int jMax=min(wn-1,c); for (int j=0;j=jMax;j+)mnj=0; for (int j=wn;j1;i-) jMax=min(wi-1,c)

20、; for (int j=0;j=jMax;j+)mij=mi+1j;for(intj=wi;j=w1) m1c=max(m1c,m2c-w1+v1);templatevoid Traceback(Type* * m,int w,int c,int n,int x) for (int i=1;i=n;i+) if(mic=mi+1c) xi=0; else xi =1;c-= wi; xn=(mnc)?1:0;1 计算复杂性分析利用动态规划求解0-1背包问题的复杂度为0(minnc,2n。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高

21、效地解决问题8。2.2 0-1背包问题在回溯法中的实现2.2.1回溯法的基本原理与分析回溯是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解奉但是由于此问题解的总组合数有个，因此随着物件数n的增大，其解的空间将以n级增长，当n大到一定程度上，用此算法解决背包问题将是不现实的。下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树

22、。一旦定义了解空间的组织方法，这个空间即可按照深度优先的方法从开始结点进行搜索，利用限界函数避免移动到不可能产生解的子空间。2.2.2 0-1背包问题的实现 回溯法的算法描述回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动

23、到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和，将r加到cp (当前节点所获收益)之上，若( r+cp) bestp(目前最优解的收益)，则不需搜索右子树。一种更有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量， 当遇到第一个不能全部放人背包的对象时， 就使用它的一部分。 解0-1背包问题的回溯算法描述如下：templateclass Knap friend Typep Knapsack(Typep*,Typew*,Typew,int); private：Typep Bound

24、(int i);void Backtrack(int i);Typew c; /背包容量 int n; /物品数Typew*w; /物品重量数组Typep*p; /物品价值数组Typew cw; /当前重量Typep cp; /当前价值Typep bestp; /当前最优价值templatevoid knap:Backtrack(int i) if(in)/到达叶结点bestp=cp;return;if(cw+wibestp) /进入右子数Backtrack(i+1);templateTypep Knap:Bound(int i)/计算上界 Typew cleft=c-cw; /剩余容量 Ty

25、pep b=cp; /以物品单位重量价值递减序装入物品 while (i=n&wi=cleft) cleft-=wi; b+=pi; i+; /装满背包if(i=n)b+=pi* cleft/wi;return b;class Object friend int Knapsack(int*,int *,int,int);public; int operator=a.d); private: int ID; float d;templateTypep Knapsack(Typep p, Typep w,Typew c,int n) /为Knap:Backtrack 初始化 Typew W=0;

26、Typep P=0; Object*Q=new Objectn; for(int i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; p+=pi; w+=wi;if(w=c)return P;/装入所有物品 /依物品单位重量价值排序 sort(Q,n); KnapK; K.p=new Typepn+1; K.w=new Typewn+1; for (int i=1;i=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回搠搜索 K.Backtrack(1);

27、deleteQ; deleteK.w; deleteK.p; reture K,bestp;1 算法效率 由于计算上界函数需要O(n)时间，在最坏情况下有O()个右孩子结点需要上界函数，故计算0-1背包问题的回溯算法所需的计算时间复杂度为O(n)。对回溯法的改进主要是对判断是否移动右子树上，一种更有效的方法是按效益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。回溯算法的运行时间取决于它在搜索过程中所生成的结点数,而限界函数可以大量减少所生成的结点个数,省去许多无谓的搜索, 使得搜索速度更快 ,其调用限界函数计算

28、上界需花费O(n)时间 ,最坏情况下有O()个结点需调用限界函数 ,需花费O(n)时间,所以该算法的时间复杂度为O(n)12。 回溯法的另一个重要特性就是在搜索执行的同时产生解空间 在搜索期间的任何时刻 仅保留从开始结点到当前可扩展结点的路径其空间需求为O(从开始结点起最长路径的长度),所以 ,此处该算法的空间复杂度为O(n),回溯法是算法设计的基本方法之一 ,它适用于解一些涉及到寻找一组解的问题或者求满足某些约束条件的最优解的问题,且适用于求解组合数量较大的问题。2.3 0-1背包问题在分枝-限界法中的实现2.3.1分枝-限界法的基本原理与分析 分枝限界发是另一种系统地搜索解空间的方法，它与

29、回溯法的主要区别在于对E-结点(expansion node)的扩充方式。每个活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出(最优)可行解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。 有两种常用的方法可用来选择下一个E-结点: 先进先出(FIFO)即从活结点表中取出结点的顺序与加人结点的顺序相同，因此活结点表的性质与队列相同。 最小耗费或最大收益法在这种模式中，每个结点都有一个对应的耗费或收益。如果查找

30、一个具有最小耗费的解，则活结点表可以最小堆来建立，下一个E-结点就是具有最小耗费的活结点，如果希望搜索一个具有最大收益的解， 则可用最大堆来构造活结点表，下一个E-结点是具有最大收益的活结点15。2.3.2 0-1背包问题的实现工作在解空间树上的FIFO分枝定界方法非常类似于从根结点出发的宽度优先搜索。它们的主要区别时在FIFO分枝定界中不可行的结点不会被搜索。0-1背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点的收益上限upprofit，使得以活结点为根的子树中的任一结点的收益值都不可能超过upprofit，活结点的最大堆使用upprofit作为关键值域。在子集树中执行最大收益分

31、枝定界搜索的函数首先初始化活结点的最大堆，并使用一个数组bestx来记录最优解。由于需要不断地利用收益密度来排序，物品的索引值会随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。函数中的循环首先检验E-结点左孩子的可行性，如它是可行的，则将它加入子集树及活结点队列(即最大堆)，仅当结点右子树的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中。则主要算法描述为：class Object friend int Knapsack(int *,int *,int,int,int *); public: int operator=a.d); private: int ID; floa

32、t d;/单位重量价值template class Knap;class bbnode friend Knap; friend int Knapsack(int *,int *,int,int,int *); private: bbnode *parent; /指向父结点的指针 bool LChild; /左儿子结点标志template class HeapNode friend Knap; public: operator Typep () const return uprofit; private: Typep uprofit, /结点的价值上界 profit; /结点所相应的价值 Typ

33、ew weight; /结点所相应的重量 int level; /活结点在子集树中所处的层序号 bbnode *ptr; /指向活结点在子集树中相应结点的指针templateclass Knap friend Typep Knapsack(Typep *,Typew *,Typew,int,int *); public: Typep MaxKnapsack(); private: MaxHeapHeapNode*H; Typep Bound(int i); void addLiveNode(Typep up,Typep cp,Typep cw,bool ch,int level); bbnod

34、e *E; /指向扩展结点的指针 Typew c; /背包容量 int n; /物品总数 Typew *w; /物品重量数组 Typep *p; /物品价值数组 Typew cw; /当前装包重量 Typep cp; /当前装包价值 int * bestx; /最优解 templateTypep Knap:MaxKnapsack()/优先队列式分支限界法，返回最大价值，bestx返回最优解 /定义最大堆的容量为1000 H=new MaxHeapHeapNode(1000); /为bestx分配存储空间 bestx=new intn+1; /初始化 int i=1; E=0; cw =cp =

35、0; Typep bestp =0; /当前最优值 Typep up =Bound(1); /价值上界 /搜索子集空间树 while(i!=n+1)/ 非叶结点 /检查当前扩展结点的左儿子结点 Typew wt =cw +wi; if(wtbestp)bestp=cp+pi; AddliveNode(up,cp+pi,cw+wi,ture,i+1); up =Bound(i+1); /检查当前扩展结点的右儿子结点 if(up=bestp)/右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1); /取下一扩展结点 HeapNodeN; H-deleteMax(N);

36、 E=N.ptr; cw=N.weight; cp=N.profit; up=N.uprofit; i=N.level; /构造当前最优解 for(int j=n;j0;j-) bestxj=E-LChild; E=E-parent; return cp; 12.4 0-1背包问题在遗传算法中的实现2.4.1遗传算法的基本原理与分析 遗传算法作为一种解决复杂问题的有效方法是在1975年首次由美国密西根大学的Hol-land教授和他的同事们借鉴生物界自然选择和进化机制基础之上提出的，它是基于生物进化中自然选择、适者生存和物种遗传思想的一种搜索算法。它将问题的每一个可能解看作是群体中的一个个体(染

37、色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。算法将根据适应值进行寻优过程。遗传算法的寻优过程是通过选择、杂交和变异等遗传算子来具体实现的，它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的每一个点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理和隐式并行性得以解释。在遗传算法中，定义长度较短、低阶且适应值超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论成为遗传算法的基本定理。 遗传算法可看成是在一个定义域为L维的向量空问B。中有一适应度函数，依其适应度大小，随机

38、进行选择、交叉和变异操作来求此函数的最大值，即将遗传算法看成是在某个空间进行求最大值的搜索技术。在操作中，新点主要是由交叉操作产生。传统的交叉算子是随机操作，后代简单地继承了“父母”的一部分基因，并不能保证子代的性能优于父辈，而且以这种方式点对点的搜索范围有限，可能会忽略邻域内更好的点而使结果收敛于局部最优。2.4.2 0-1背包问题的实现 (1) 编码方案: 用遗传算法来求解0-1背包问题，一种很自然的编码方案是将待求解的各量X表示成长为n的二进制字符串Xi,j=1,2,n,xi=1表示物体j 放人背包，xj表示物体j放入背包。(2) 适应度函数的设计: 基于上述编码，按照所提出的罚函数 处

39、理约束条件的方法构造背包问题的适应度函数 (X):(X)=-这里，对于所有满足条C的可行解X，惩罚函数Va(X)=0 惩罚函数可以使用对数函数，线性函数，二次函数等，分别随侵犯的程度增加而顺序采用。 (3) 选择操作：根据选择概率选择染色体，将上述的个体作为第0代。对于每个染色体，计算累积概率Qi，从区间(0, Qi) 种产生一个随机数r，若Qi -1rQi，则选择第i个染色体，重复上述操作，复制染色体。 (4) 交叉操作：判断染色体是否为活的染色体，若为活的染色体，则将染色体进行交叉，一般采用单点交叉方式。 (5) 变异操作：染色体变异采用位点变异的方式。使变异后的适应度至少大于等于原适应度

40、，否则重新选择变异位进行变异，如此重复若干次，若适应度值没有提高，则变异失败。 (6) 当某代得到的结果满足要求或当前代数等于结束代数时算法结束得到结果，否则重复上述步骤(3)、(4) 7。 则主要算法描述为：procedure search(k,v:integer); 搜索第k个物品，剩余空间为v var i,j:integer; begin if v=best then exit; sn为前n个物品的重量和 if kwk then search(k+1,v-wk); search(k+1,v); end; end; l DP Fi,j为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。实现:A:将最优化问题转化为判定性问题 f i, j = f i-1, j-wi (wI=j0 then if j+now=n then inc(cj+now,aj); a:=c; end9;3 解0-1背包问题的算法比较与分析这四种算法都得到了验证，运行结果证明了算法设计是可行的，正确的。通过