华中师范大学汉口分校 本 科 毕 业 论 文
0-1背包问题的算法研究与实现
院 系：信息科学技术学院 专 业：计算机科学与技术
年 级： 2005级 学 生： 刘念 学 号： 2005911032 指导老师： 宾云峰、杨健
华中师范大学汉口分校 学位论文原创性声明
本人郑重声明：所呈交的学位论文是本人在导师指导下独立进行研究工作所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。
学位论文作者签名： 日期： 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
本学位论文属于
1、保密 □ ，在_____年解密后适用本授权书。 2、不保密 □。
（请在以上相应方框内打“√”）
学位论文作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日
目 录
内容摘要............................................................ 1 关 键 词............................................................ 1 ABSTRACT............................................................ 2 KEY WORDS........................................................... 2 1 绪论.............................................................. 3 1.1问题的提出及研究意义 .......................................... 3 1.2 0-1背包问题的算法研究的分析 .................................. 3 1.3课题的主要研究内容 ............................................ 4 2 0-1背包问题的实现 ................................................ 5 2.1 0-1背包问题在动态规划中的实现 ................................ 5 2.2 0-1背包问题在回溯法中的实现 .................................. 8 2.3 0-1背包问题在分枝-限界法中的实现 ............................ 12 2.4 0-1背包问题在遗传算法中的实现 ............................... 16 3 解0-1背包问题的算法比较与分析................................... 20 4总结与展望 ....................................................... 22 参考文献........................................................... 23 致 谢............................................................. 25
3
内容摘要：背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。
那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用动态规划法，回溯法，分枝-限界法，遗传算法四种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结四种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。
关 键 词：0-1背包 动态规划 回溯法 分枝-限界法 遗传算法
1
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, 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 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, branch - 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 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 knapsack 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 - Bound method genetic algorithm
2
背包问题的算法研究与实现本科毕业论文 精品
