《背包问题的算法研究与实现本科毕业论文》由会员分享，可在线阅读，更多相关《背包问题的算法研究与实现本科毕业论文（28页珍藏版）》请在金锄头文库上搜索。
1、. . . . 华中师大学汉口分校本 科 毕 业 论 文0-1背包问题的算法研究与实现院 系：信息科学技术学院 专 业：计算机科学与技术 年 级： 2005级 学 生： 念 学 号： 2005911032 指导老师： 宾云峰、健 / 华中师大学汉口分校学位论文原创性声明本人重声明：所呈交的学位论文是本人在导师指导下独立进行研究工作所取得的研究成果。除了文中特别加以标注引用的容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。学位论文作者签名： 日期： 年 月 日学位论文使用授权书本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校
2、保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部或部分容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、 ，在_年解密后适用本授权书。2、不 。（请在以上相应方框打“”）学位论文作者签名： 日期： 年 月 日导师签名： 日期： 年 月 日目 录容摘要1关键词1ABSTRACT2KEY WORDS21 绪论31.1问题的提出与研究意义31.2 0-1背包问题的算法研究的分析31.3课题的主要研究容42 0-1背包问题的实现52.1 0-1背包问题在动态规划中的
3、实现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背包 动态规划 回溯法分枝-限界法遗传算法Abstract：Knapsack problem is a typic
5、al 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, a lot of classical methods solving this problem have been c
6、ome 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 the 0-1 knapsack problem .So to solve the knapsack problem,
7、 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, branch - Bound method and genetic algorithm respectively aiming a
8、t 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 basic idea of algorithm by using specific examples in solvin
9、g 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 knapsack problem into the practical, and to design targeted f
10、or 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 problemdynamic programmibacktrackingbranch - Bound methodgenetic algorithm1 绪论1.1问题的提出与研究意义0-1背包问题是计算机科学中的一个非
11、常经典的优化问题。也是被证明了的NP难度问题。它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法
12、。多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。1.2 0-1背包问题的算法研究的分析0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。0-1背
13、包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。它包含了背包问题中设计状态、方程的最基本思想，在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属于NP-C完全问题，其计算复杂度，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。1.3课
14、题的主要研究容1.3.1背包问题的描述背包问题是整数规划中的一类特殊问题，在现实生活中具有广泛应用。如果能提出求解此问题的有效算法，则具有很好的经济价值和决策价值。问题的一般描述是：旅行者背包登山，背包的最大承重为M，现有n个物品可供选择装入背包，第i个物品莺量为wi，价值为pi，假定物品i的一部分xi(0xi1)放人背包，获得价值为xipi，由于背包最大承重为M，要求装入物品总质量不过超过M，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。背包问题的数学描述如下：要求找到一个n元向量(x1，x2xn)，在满足约束条件：情况下，使得目标函数，其中，1in；M0；wi0；pi
15、0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解1。 1.3.2 0-1背包问题 0-1背包问题的提出给定n 种物品和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。 问题符号化 0-1背包问题的符号化表示是，给定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 动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，
