刘念-2005911032-0-1背包问题的算法研究与实现

华中师范大学汉口分校本科毕业论文0-1背包问题的算法研究与实现院系：信息科学技术学院专业：计算机科学与技术年级：2005级学生：刘念学号：2005911032指导老师：宾云峰、杨健华中师范大学汉口分校学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师指导下独立进行研究工作所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密□，在_____年解密后适用本授权书。2、不保密□。（请在以上相应方框内打“√”）学位论文作者签名：日期：年月日导师签名：日期：年月日3目录内容摘要........................................................................................................................1关键词........................................................................................................................1ABSTRACT........................................................................................................................2KEYWORDS......................................................................................................................21绪论............................................................................................................................31.1问题的提出及研究意义.....................................................................................31.20-1背包问题的算法研究的分析.....................................................................31.3课题的主要研究内容.........................................................................................420-1背包问题的实现.................................................................................................52.10-1背包问题在动态规划中的实现.................................................................52.20-1背包问题在回溯法中的实现.....................................................................82.30-1背包问题在分枝-限界法中的实现.........................................................122.40-1背包问题在遗传算法中的实现...............................................................163解0-1背包问题的算法比较与分析......................................................................204总结与展望...............................................................................................................22参考文献......................................................................................................................23致谢..........................................................................................................................251内容摘要：背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用动态规划法，回溯法，分枝-限界法，遗传算法四种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结四种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。关键词：0-1背包动态规划回溯法分枝-限界法遗传算法2Abstract：KnapsackproblemisatypicalNP-Cproblemaswellasalgorithmdesignandanalysisoftheclassicalproblemsinthecommonfieldofoperationsresearch.Itisveryimportanttostudythesolutionoftheproblem,whetherintheoryorinpractice.Aftersomeresearch,alotofclassicalmethodssolvingthisproblemhavebeencomeupwith,andtheexplorationofthisissueandappliedresearchhasbeenongoing.Undertheguidanceofadvancedtheory,therearedistinctivefeaturessuchasscientific,efficient,economic,flexibleandconvenientfeaturesinsolvingthe0-1knapsackproblem.Sotosolvetheknapsackproblem,thefirstpremiseistodesignagoodalgorithm.Toseekthesolutionofknapsackproblem,itisnecessarytodesignalgorithmsusingdynamicprogrammingatfirst.Inthispaper,fourmethodssuchasdynamicprogramming,backtracking,branch-Boundmethodandgeneticalgorithmrespectivelyaimingatknapsackproblem,0-1knapsackproblemandasimple0-1knapsackproblemcarryoutthealgorithmdesignandanalysisoftimecomplexity,andgivethespecificalgorithmdesignandimplementationoftheprocess.Anddescriptdetailedlythebasicideaofalgorithmbyusingspecificexamplesinsolvingtheissuewithdifferentways.Andthenaimingatsolvingthe0-1knapsackproblem,comparefouralgorithmsindetailandsummarizetheadvantagesanddisadvantagesofrealizationoffourmethodsandreachaconclusion.Howtoapplytheknapsackproblemintothepractical,andtodesigntargetedforthepracticalalgorithmsofsolving0-1KnapsackProblemandtosolvethepracticalproblemsverywell,isanareaofcomputerworkers’constantlythinkingandstudy.Keywords：0-1knapsackproblemdynamicprogrammibacktrackingbranch-Boundmethodgeneticalgorithm31绪论1.1问题的提出及研究意义0-1背包问题是计算机科学中的一个非常经典的优化问题。也是被证明了的NP难度问题。它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法。多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。1.20-1背包问题的算法研究的分析0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。0-1背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程