背包问题的算法研究与实现_学位论文.doc

《背包问题的算法研究与实现_学位论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中师范大学汉口分校本科毕业论文0-1背包问题的算法研究与实现院系：信息科学技术学院专业：计算机科学与技术年级：2005级学生：刘念学号：2005911032指导老师：宾云峰、杨健25华中师范大学汉口分校学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师指导下独立进行研究工作所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向有关学位论文管

2、理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密□，在_____年解密后适用本授权书。2、不保密□。（请在以上相应方框内打“√”）学位论文作者签名：日期：年月日导师签名：日期：年月日25目录内容摘要1关键词1ABSTRACT2KEYWORDS21绪论31.1问题的提出及研究意义31.20-1背包问题的算法研究的分析31.3课题的主要研究内容420-1背包问题的实现52.10-1背包问题在动态规

3、划中的实现52.20-1背包问题在回溯法中的实现82.30-1背包问题在分枝-限界法中的实现122.40-1背包问题在遗传算法中的实现163解0-1背包问题的算法比较与分析204总结与展望22参考文献23致谢2525内容摘要：背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题，首要的前提就是设计

4、出好的算法，想求得背包问题的解，就要先设计出算法,本文采用动态规划法，回溯法，分枝-限界法，遗传算法四种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结四种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。关键词：0-1背包动态规划回溯法分枝-限界法遗传算法25Abstract：

5、KnapsackproblemisatypicalNP-Cproblemaswellasalgorithmdesignandanalysisoftheclassicalproblemsinthecommonfieldofoperationsresearch.Itisveryimportanttostudythesolutionoftheproblem,whetherintheoryorinpractice.Aftersomeresearch,alotofclassicalmethodssolvingthisproblemhavebeencomeupwith,andth

6、eexplorationofthisissueandappliedresearchhasbeenongoing.Undertheguidanceofadvancedtheory,therearedistinctivefeaturessuchasscientific,efficient,economic,flexibleandconvenientfeaturesinsolvingthe0-1knapsackproblem.Sotosolvetheknapsackproblem,thefirstpremiseistodesignagoodalgorithm.Toseekt

7、hesolutionofknapsackproblem,itisnecessarytodesignalgorithmsusingdynamicprogrammingatfirst.Inthispaper,fourmethodssuchasdynamicprogramming,backtracking,branch-Boundmethodandgeneticalgorithmrespectivelyaimingatknapsackproblem,0-1knapsackproblemandasimple0-1knapsackproblemcarryout