4总结与展望

本文就回溯法，分枝-限界法，遗传算法这4种求解0-1背包问题的方法进

行研究比较，全方位的了解背包问题在实现的方法,以及各方法的优势和劣势，通过比较，了解哪种方法是在什么样的情况下是最实用的方法，然后在以后的实际运用中针对实际问题，找到最简单的方法解决0-1背包问题。

当然目前存在越来越多的算法来研究0-1背包问题，比如蚁群算法、微粒群算法等群体智能算法在0-1背包问题求解方面具有的较好收敛速度、健壮性、稳定性、算法简单等优点.最后,针对群体智能算法在求解0-1背包问题过程中所出现的缺陷,提出了群体智能算法在0-1背包问题，还有一写混合的多有算法来解决0-1背包问题等等

0-1背包问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。

22

参考文献

[1] 王晓东.《计算机算法研究与分析》.电子工业出版社.

[2] M.H.Alsuwaiyel著，吴伟昶，方世昌等译.《算法设计技巧与分析》. 电子工业出版社, 2004.

[3] 胡运权，运筹学教程（第二版），清华大学出版社，2003年. [4] 曹新谱.《算法设计与分析》.湖南科技出版社，1984年11月第1版 . [5] 余祥宣. 崔国华. 邹海明. 计算机算法[M].华中科技大学出版社，2003.

[6] 李鸣山.郑海虹. 0-1背包间题的多重分枝-限界算法 .武汉侧绘科技大学学报，1995 . 20 (1).

[7] 霍红卫.许进.保铮.基于遗传算法的0-1背包问题求解.西安电子科技大学学报， 1995.26（4）.

[8] 刘西奎.李艳.许进.背包问题的遗传算法求解研究阴.华中科技大学学报(自然科学版)，2002，30(6)：89-90.

[9] Mark Allen weiss著.冯舜玺译. 数据结构与算法分析—C语言描述[M].北京: 机械工业出版社， 2004. 1.

[10] 卢开澄.计算机算法引导-设计与分析(第2 版)[M]=.北京:清华大学出版社，2006.

[11] 郑宗汉.郑晓明. 算法设计与分析[M].北京:清华大学出版社，2005. [12] 陈莹.廖利.0-1 背包问题[J].电脑知识与技术_研究开发，2005.5:96-97.

[13] 朱红.算法设计与分析[M].上海：上海科学技术文献出版社，1989． [14] 张文修.梁怡.遗传算法的数学基础[M].西安:西安交通犬学出版社，2001.

[15] COILEM TH，LEISERSON CE Introducetion to Algorithms[M]。Massachusetts：The MIT Press，2002.

[16] 曾国清.0-l背包问题的遗传算法求解[J]．科技信息,2006(3):242一243．

[17] 黄波.蔡之华. 0/1背包问题及其解法研究 0/1 Knapsack Problem and Its Solution Methods Study 期刊电脑知识与技术(学术交流)COMPUTER

23

KNOWLEDGE AND TECHNOLOGY ，2007年 第07期.

[18] 雷鹏, 朱大铭, 马绍汉, 0/1背包问题算法研究新趋势2001年全国理论计算机科学学术会议2001年全国理论计算机科学学术会议论文集， 2001年.

[19] 张景成,戴光明 基于0/1背包问题的算法探究 On the Algorithm of the 0/1 Knapsack Problem 期刊 电脑知识与技术（学术交流）COMPUTER KNOWLEDGE AND TECHNOLOGY，

年 第11期.

24

2007

致 谢

弹指一挥间，四年的大学学习即将结束。在此，我要感谢华中师范大学汉口分校信息科学与技术学院的各位领导和老师们，感谢关心帮助过我的同学们。本文之得以完成，要特别感谢我的指导老师宾云峰、杨健老师。从论题的选择、资料的收集、系统的研发到论文的写作，都是在宾云峰、杨健老师的悉心指导和殷切关怀下完成的。他们严谨的治学精神、渊博的理论知识和丰富的实践经验使我受益匪浅。在此，我向尊敬的宾云峰、杨健老师致以崇高的敬意和衷心的感谢!

同时，向参加论文审阅和答辩的各位专家和老师表示衷心的感谢。

25