0-1背包问题研究及算法策略比较分析

数学与物理科学学院《算法分析与设计》课程考查论文题目0-1背包问题研究及算法策略比较分析专业班级学号姓名任课教师完成日期2011/5/24成绩摘要背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结这种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。目录摘要...............................................................2一、绪论...........................................................41.1问题的研究及意义.....................................................................................................................41.20-1背包问题的算法研究与分析..............................................................................................41.3课题的主要研究内容.................................................................................................................4二、0-1背包问题在动态规划中的实现..................................52.1动态规划的基本原理与分析.....................................................................................................52.20-1背包问题的实现..................................................................................................................5三、0-1背包问题在分枝-限界法中的实现...............................73.1分枝-限界法的基本原理与分析................................................................................................73.20-1背包问题的实现..................................................................................................................7四、0-1背包问题在遗传算法中的实现..................................94.1遗传算法的基本原理与分析......................................................................................................94.20-1背包问题的实现................................................................................................................10五、0-1背包问题在回溯法中的实现...................................115.1回溯法的基本原理与分析.......................................................................................................115.20-1背包问题的实现................................................................................................................115.30-1背包问题在回溯法中的算法描述....................................................................................125.4算法效率...................................................................................................................................145.5运行结果...................................................................................................................................15六、四种算法的比较与分析..........................................15七、附录..........................................................17一、绪论1.1问题的研究及意义0-1背包问题是计算机科学中的一个非常经典的优化问题。它的主要思路是假定某人拥有大量物品，重量各不同。通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法。多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。1.20-1背包问题的算法研究与分析0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。0-1背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。它包含了背包问题中设计状态、方程的最基本思想，在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属于NP-C完全问题，其计算复杂度，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。1.3课题的主要研究内容问题的一般描述是：旅行者背包登山，背包的最大承重为M，现有n个物品可供选择装入背包，第i个物品莺量为wi，价值为pi，假定物品i的一部分xi(0xi1)放人背包，获得价值为xipi，由于背包最大承重为M，要求装入物品总质量不过超过M，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。背包问题的数学描述如下：要求找到一个n元向量(x1，x2…xn)，在满足约束条件：10iiixMwx情况下，使得目标函数pxiimax，其中，1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解[1]。给定n种物品和1个背包。物品i的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。0-1背包问题的符号化表示是，给定M0，wi0，pi0，1in，要求找到一个n元0-1向量向量(x1，x2…xn)，Xi=0或1,1in,使得Mwxii，而且pxii达到最大[2]。二、0-1背包问题在动态规划中的实现2.1动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：①分析最优解的结构：最有子结构性质；②建立递归方程；③计算最优值；④构造最优解[4]。2.20-1背包问题的实现①最优子结构性质0-1背包问题具有最优子结构性质。设(y1，y2…yn)是所给0-1背包问题的一个最优解，则(y2，y3…yn)是下面相应子问题的一个最优解：nikkkxvmaxnkixjxwknikkk},1,0{因若不然，设(z2，z3…zn)是上述问题的一个最优解，而(y2，y3…yn)不是它的最优解，由此可见ni2niiiyv2,且niiizw2w1y1c。因此niiizv2v1y1niiiyv1niiizw2w1y1c这说明(y1，z2…zn)是所给0-1背包问题的一个更优解，从而(y1，y2…yn)不是所给0-1背包问题的最优解。此为矛盾[1]。②递归关系设所给0-1背包问题的子问题nikkkxvmaxnkixjxwknikkk},1,0{的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为i，i+1，……，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：wjjjimwijviwijimjim0),,1(},),1(),),1(max{j)m(i,