华中师范大学汉口分校 本 科 毕 业 论 文

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