0-1背包问题的各种算法分析

《0-1背包问题的各种算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码10125专业代码ShanxiUniversityofFinanceandEconomics本科毕业论文题目：0-1背包问题的各种算法分析学院：应用数学学院专业：信息与计算科学学号：0姓名：刘波指导教师：冯俊2008年4月30日修德立信博学求真毕业论文学术承诺本人郑重承诺：所呈交的毕业论文是我个人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不存在抄袭情况，论文中不包含其他人已经发表的研究成果，也不包含他人或其他教学机构取得研究成果。作者签名：日期：毕业论文使

2、用授权的说明本人了解并遵守山西财经大学有关保留、使用毕业论文的规定。即：学校有权保留、向国家有关部门送交毕业论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。（保密的论文在解密后应遵守此规定）作者签名：指导教师签名：日期：日期：目录中文摘要Ⅰ英文摘要Ⅱ第一章绪论1第一节课题的研究意义与背景1第二节0-1背包问题描述2第二章0-1背包问题经典算法分析3第一节贪心算法3一、算法思想3二、算法描述4三、算法分析4第二节动态规划算法4一、算法思想5二、算

3、法步骤及描述5三、算法分析6第三节回溯法7一、算法思想7二、算法步骤及描述9三、算法分析9第四节分支限界法9一、算法思想9二、算法分析10第五节蚁群算法11一、算法思想11二、算法步骤及描述12三、算法分析12参考文献13致谢14山西财经大学毕业论文（设计）0-1背包问题的各种算法分析摘要：0/1背包问题是计算机算法中一个经典问题。半个世纪以来，该问题一直是算法与复杂性研究的热点之一。目前,贪心算法、动态规划算法、回溯法、分支限界法和蚁群算法是求解0/1背包问题的主要算法,从各种算法设计思想入手,并进行理论

4、分析。论文中所做的主要工作如下:(1)介绍各种算法思想。(2)对各种算法进行算法描述。(3)将各种算法进行分析，了解各自的利弊及适用范围。关键词：0-1背包问题；贪心算法；动态规划算法；回溯法；分支限界法；蚁群算法山西财经大学毕业论文（设计）0-1knapsackproblemalgorithmsanalysisAbstract：0/1knapsackproblemisaclassicalprobleminalgorithmfield.TheProblemhasbeenahotsPotinalgorlthm

5、andcomPlexityresearchfieldinhalfacentury.Atpresent,greedyalgorithm、dynamicprograming、backtracingmethod、branchandboundmethodandantcolonyalgorithmisresolvethemainmethodof0/1knapsackproblem.Fromallkindsofalgorithmbegin,thesealgorithmsareanalyzedintheory.hethe

6、siscontributestothefollowingworks.(1)Introduceavarietyofalgorithms.(2)Thevariousalgorithmsarediscribedinalgorithm.(3)Variousalgorithmsareanalyzed,theadvantagesanddisadvantagesandapplicablescopeofknowledge.Keywords：0-1KP;greedyalgorithm；dynamicprograming；ba

7、cktracingmethod；branchandboundmethod；antcolonyalgorithm山西财经大学毕业论文（设计）第一章绪论第一节课题的研究意义与背景O-1背包问题是一个NP难解问题，它在很多领域都有广泛的应用。很多实际问题都可转换为0-1背包问题，例如下料问题、贷款组合优化决策问题等。0-l整数线性规划问题可以归结为O-1背包问题，而整数线性规划问题都可以转化为0-l整数线性规划问题。同时，0-1背包问题在信息加密[1-2]、预算控制、项目选择、材料切割、货物装载、网络信息安全等应

8、用中具有重要的价值。所以，对0-1背包问题求解方法的研究无论是在理论上还是在实践中都具有一定的意义。Dantzing在20世纪50年代首先对该问题进行了开创性的研究，利用贪心法求得了0-1背包问题最优解的上界［3］。1974年，Horowitz和Salmi利用分支限界法解答了背包问题［4］，并提出背包问题的可分性，指出了求解该问题的一条新途径。随后，Balas和Zemel提出了背包问题的“核”思想［5］，使背包问