《算法分析与设计》课程设计背包问题研究及算法策略比较分析.docVIP

成 绩 数学与物理科学学院 《算法分析与设计》课程考查论文 题 目　0-1背包问题研究及算法策略比较分析 专 业　 班 级　 学 号　 姓 名　 任课教师　 完成日期 2011/5/24 摘要 背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。 那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结这种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。 目录 摘要 2 一、绪论 4 1.1问题的研究及意义 4 1.2 0-1背包问题的算法研究与分析 4 1.3课题的主要研究内容 5 二、0-1背包问题在动态规划中的实现 5 2.1 动态规划的基本原理与分析 5 2.2 0-1背包问题的实现 6 三、0-1背包问题在分枝-限界法中的实现 8 3.1分枝-限界法的基本原理与分析 8 3.2 0-1背包问题的实现 9 四、0-1背包问题在遗传算法中的实现 12 4.1遗传算法的基本原理与分析 12 4.2 0-1背包问题的实现 12 五、0-1背包问题在回溯法中的实现 14 5.1回溯法的基本原理与分析 14 5.2 0-1背包问题的实现 15 5.3 0-1背包问题在回溯法中的算法描述 15 5.4 算法效率 19 5.5 运行结果 20 六、四种算法的比较与分析 20 七、附录 22 一、绪论 1.1问题的研究及意义 0-1背包问题是计算机科学中的一个非常经典的优化问题。它的主要思路是假定某人拥有大量物品，重量各不同。通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是必威体育官网网址的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法。 多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。 1.2 0-1背包问题的算法研究与分析 0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。0-1背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。它包含了背包问题中设计状态、方程的最基本思想，在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属于NP-C完全问题，其计算复杂度，传统上采用动态规划来求解。背包问