华中师范大学汉口分校本科毕业论文0-1背包问题的算法研究与实现院系：信息科学技术学院专业：计算机科学与技术年级：2005级学生：刘念学号：2005911032指导老师：宾云峰、杨健华中师范大学汉口分校学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师指导下独立进行研究工作所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密□，在_____年解密后适用本授权书。2、不保密□。（请在以上相应方框内打“√”）学位论文作者签名：日期：年月日导师签名：日期：年月日目录TOC\o"1-2"\h\z\uHYPERLINK\l"_Toc230679042"内容摘要PAGEREF_Toc230679042\h1HYPERLINK\l"_Toc230679043"关键词PAGEREF_Toc230679043\h1HYPERLINK\l"_Toc230679044"AbstractPAGEREF_Toc230679044\h2HYPERLINK\l"_Toc230679045"KeywordsPAGEREF_Toc230679045\h2HYPERLINK\l"_Toc230679046"1绪论PAGEREF_Toc230679046\h3HYPERLINK\l"_Toc230679047"1.1问题的提出及研究意义PAGEREF_Toc230679047\h3HYPERLINK\l"_Toc230679048"1.20-1背包问题的算法研究的分析PAGEREF_Toc230679048\h3HYPERLINK\l"_Toc230679049"1.3课题的主要研究内容PAGEREF_Toc230679049\h4HYPERLINK\l"_Toc230679050"20-1背包问题的实现PAGEREF_Toc230679050\h5HYPERLINK\l"_Toc230679051"2.10-1背包问题在动态规划中的实现PAGEREF_Toc230679051\h5HYPERLINK\l"_Toc230679052"2.20-1背包问题在回溯法中的实现PAGEREF_Toc230679052\h8HYPERLINK\l"_Toc230679053"2.30-1背包问题在分枝-限界法中的实现PAGEREF_Toc230679053\h12HYPERLINK\l"_Toc230679054"2.40-1背包问题在遗传算法中的实现PAGEREF_Toc230679054\h16HYPERLINK\l"_Toc230679055"3解0-1背包问题的算法比较与分析PAGEREF_Toc230679055\h20HYPERLINK\l"_Toc230679056"4总结与展望PAGEREF_Toc230679056\h22HYPERLINK\l"_Toc230679057"参考文献PAGEREF_Toc230679057\h23HYPERLINK\l"_Toc230679058"致谢PAGEREF_Toc230679058\h25内容摘要：背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用动态规划法，回溯法，分枝-限界法，遗传算法四种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就