背包问题的算法研究与实现本科.doc
《背包问题的算法研究与实现本科.doc》由会员分享,可在线阅读,更多相关《背包问题的算法研究与实现本科.doc(28页珍藏版)》请在三一文库上搜索。
1、华中师范大学汉口分校华中师范大学汉口分校 本本 科科 毕毕 业业 论论 文文 0-10-1 背包问题的算法研究与实现背包问题的算法研究与实现 院院 系:系:信息科学技术学院信息科学技术学院 专专 业:业:计算机科学与技术计算机科学与技术 年年 级:级: 20052005 级级 学学 生:生: 刘念刘念 学学 号:号: 20059110322005911032 指导老师:指导老师: 宾云峰、杨健宾云峰、杨健 华中师范大学汉口分校 学位论文原创性声明 本人郑重声明:所呈交的学位论文是本人在导师指导下独立进行研究工作 所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何 其他个人或集
2、体已经发表或撰写的成果作品。本人完全意识到本声明的法律后 果由本人承担。 学位论文作者签名: 日期: 年 月 日 学位学位论论文版文版权权使用授使用授权书权书 本学位论文作者完全了解学校有关保障、使用学位论文的规定,同意学校 保留并向有关学位论文管理部门或机构送交论文的复印件和电子版,允许论文 被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部 或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 本学位论文属于 1、保密 ,在_年解密后适用本授权书。 2、不保密 。 (请在以上相应方框内打“” ) 学位论文作者签名: 日期: 年 月
3、日 导师签名: 日期: 年 月 日 3 目目 录录 内容摘要1 关 键 词1 ABSTRACT2 KEY WORDS.2 1 绪论3 1.1 问题的提出及研究意义 3 1.2 0-1 背包问题的算法研究的分析.3 1.3 课题的主要研究内容 4 2 0-1 背包问题的实现 5 2.1 0-1 背包问题在动态规划中的实现.5 2.2 0-1 背包问题在回溯法中的实现.8 2.3 0-1 背包问题在分枝-限界法中的实现.12 2.4 0-1 背包问题在遗传算法中的实现16 3 解 0-1 背包问题的算法比较与分析.20 4 总结与展望 .22 参考文献.23 致 谢.25 1 内容摘要内容摘要:背
4、包问题是一个在运筹学领域里常见的典型 NP-C 难题,也是算 法设计分析中的经典问题,对该问题的求解方法的研究无论是在理论上,还是在 实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法,对 该问题的探索和应用研究一直在进行。在先进理论指导下,求解 0-1 背包问题 具有科学、高效、经济、灵活、方便等显著特点。 那么要解决背包问题,首要的前提就是设计出好的算法,想求得背包问题 的解,就要先设计出算法,本文采用动态规划法,回溯法,分枝-限界法,遗传 算法四种方法分别对背包问题、0-1 背包问题及简单 0-1 背包问题进行算法设 计和时间复杂度分析,给出具体算法设计和实现过程。并以具体
5、实例详细描述 不同方法求解问题解时算法基本思想,然后就解决 0-1 背包问题对这四种算法 进行详细的比较,总结四种方法实现的优缺点并得出结论。如何将背包问题应 用于实际问题中,有针对性地设计适合求解实际 0-1 背包问题的算法,并很好 地解决实际问题,是计算机工作者不断思索、研究的一个领域。 关关 键键 词词:0-1 背包 动态规划 回溯法 分枝-限界法 遗传算法 2 AbstractAbstract: Knapsack problem is a typical NP-C problem as well as algorithm design and analysis of the class
6、ical problems in the common field of operations research. It is very important to study the solution of the problem, whether in theory or in practice. After some research, a lot of classical methods solving this problem have been come up with ,and the exploration of this issue and applied research h
7、as been ongoing. Under the guidance of advanced theory, there are distinctive features such as scientific, efficient, economic, flexible and convenient features in solving the 0-1 knapsack problem . So to solve the knapsack problem, the first premise is to design a good algorithm.To seek the solutio
8、n of knapsack problem, it is necessary to design algorithms using dynamic programming at first. In this paper, four methods such as dynamic programming, backtracking, branch - Bound method and genetic algorithm respectively aiming at knapsack problem ,0-1 knapsack problem and a simple 0-1 knapsack p
9、roblem carry out the algorithm design and analysis of time complexity, and give the specific algorithm design and implementation of the process.And descript detailedly the basic idea of algorithm by using specific examples in solving the issue with different ways .And then aiming at solving the 0-1
10、knapsack problem , compare four algorithms in detail and summarize the advantages and disadvantages of realization of four methods and reach a conclusion.How to apply the knapsack problem into the practical, and to design targeted for the practical algorithms of solving 0-1 Knapsack Problem and to s
11、olve the practical problems very well, is an area of computer workers constantly thinking and study. KeyKey wordswords:0-1 knapsack problem dynamic programmi backtracking branch - Bound method genetic algorithm 3 1 1 绪论绪论 1.11.1 问题的提出及研究意义问题的提出及研究意义 0-1 背包问题是计算机科学中的一个非常经典的优化问题。也是被证明了 的 NP 难度问题。它是在 1
12、978 年由 Merkel 和 Hellman 提出的。它的主要思路 是假定某人拥有大量物品,重量各不同。此人通过秘密地选择一部分物品并将 它们放到背包中来加密消息。背包中的物品中重量是公开的,所有可能选择的 物品也是公开的,但背包中的物品是保密的。附加一定的限制条件,给出重量, 而要列出可能的物品,在计算上是不可实现的。背包问题是熟知的不可计算问 题,背包体制以其加密,解密速度快而其人注目。但是,大多数一次背包体制 均被破译了,因此现在很少有人使用它。围绕这个问题的求解方法很多,比如 贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见 的一种求解方法。 多年来,背包问题吸引
13、了许多理论和实际工作者对此问题作深入的研究, 在理论上,尽管背包问题的结构简单,但它却具有组合爆炸的性质,在实际应 用中,许多工业问题都可以用背包问题来描述求解,如资金运算、货舱装载、 存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中,并很 好地解决实际问题,是计算机工作者不断思索、研究的一个领域。 1.21.2 0-10-1 背包问题的算法研究的分析背包问题的算法研究的分析 0-1 背包问题的算法研究主要是通过算法设计与分析知识,设计解决相关 问题的尽可能高效的算法并程序实现,而且能够分析算法的复杂性,通过实验 进一步领会各种算法设计技术的基本原理,掌握算法设计和分析方法,提高
14、算 法设计与分析的应用能力。 0-1 背包是一类很典型的优化问题,研究它有很重要的实际意义,这不仅是 由于它结构简洁,可以作为子问题为研究更复杂的问题奠定理论基础,有很高 的理论研究价值,而且由于它是许多实际工程应用问题的种通用化描述,在很 多实际问题当中有着非常广泛的应用背景,例如项目决策等。他是最基本的背 包问题,即对一个物体要么选用,要么就抛弃,不能将一个物体再继续细分的 4 情况。它包含了背包问题中设计状态、方程的最基本思想,在经济管理、资源 分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属于 NP-C 完全问题,其计算复杂度,传统上采用动态规划来求解。背包问题就是在
15、资源有限的条件下,追求总的最大收益的资源有效分配问题。 1.31.3 课题的主要研究内容课题的主要研究内容 1.3.11.3.1 背包问题的描述背包问题的描述 背包问题是整数规划中的一类特殊问题,在现实生活中具有广泛应用。如 果能提出求解此问题的有效算法,则具有很好的经济价值和决策价值。 问题的一般描述是:旅行者背包登山,背包的最大承重为 M,现有 n 个物 品可供选择装入背包,第 i 个物品莺量为 wi,价值为 pi,假定物品 i 的一部分 xi(0xi1)放人背包,获得价值为 xipi,由于背包最大承重为 M,要求装入物 品总质量不过超过 M,问旅行者应该如何选择物品装入背包,使得装入物品
16、的 价值总和达到最大值。 背包问题的数学描述如下:要求找到一个 n 元向量(x1,x2xn),在满足 约束条件:情况下,使得目标函数,其中, 10 i ii x Mwx p x i i max 1in;M0;wi0;pi0。满足约束条件的任何向量都是一个可行解,而使 得目标函数达到最大的那个可行解则为最优解1。 1.3.21.3.2 0-10-1 背包问题背包问题 0-1 背包问题的提出 给定 n 种物品和 1 个背包。物品 i 的重量是 wi,其价值为 pi,背包的容 量为 M。问应如何装入背包中的物品,使得装人背包中物品的总价值最大?在 选择装人背包的物品时,对每种物品 i 只有两种选择,
17、即装入背包、不装入背 包。不能将物品 i 装人背包多次,也不能只装入部分的物品 i。该问题称为 0- 1 背包问题。 问题符号化 0-1 背包问题的符号化表示是,给定 M0, w i 0, pi 0,1in , 要求找到一个 n 元 0-1 向量向量(x1,x2xn), X i =0 或 1 , 1in, 使得 5 ,而且达到最大2。Mwx ii px i i 2 2 0-10-1 背包问题的实现背包问题的实现 2.12.1 0-10-1 背包问题在动态规划中的实现背包问题在动态规划中的实现 2.1.12.1.1 动态规划的基本原理与分析动态规划的基本原理与分析 动态规划算法的基本思想是将待求
18、解问题分解成若干个子问题,先求解子 问题,然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往 不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解 决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计 算,从而得到多项式时间算法。它把已知问题分为很多子问题,按顺序求解子 问题,在每一种情况下,列出各种情况的局部解,按条件从中选取那些最有可 能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息,而减少计算 量,最后一个子问题的解即为问题解。采用此方法求解 0-1 背包问题的主要步 骤如下: 分析最优解的结构:最有子结构性质; 建立递归方程; 计算最
19、优值; 构造最优解4。 动态规划算法的每一步决策都是根据前一步的状态参量来决定这一步状态 参量的设置,也就是说,从初始状态到最终状态要经过多个过程,经历不同的 状态,不断地根据上一步状态决定下一状态,从而形成了一个决策序列,最终 将整个问题解决,这就是典型的多段决策的特性。 由上面的动态规划法的介绍,可以看出 0-1 背包问题,是符合多段决策的 特点和具有重叠子问题。因此,在设计 0-1 背包问题解决方案时,可以将整个 物品放到背包的过程,看成一个取物品的过程。 2.2.22.2.2 0-10-1 背包问题的实现背包问题的实现 最优子结构性质 0-1 背包问题具有最优子结构性质。设(y1,y2
20、yn)是所给 0-1 背包问题 的一个最优解,则(y2,y3yn)是下面相应子问题的一个最优解: 6 n ik kkx vmax nkix jxw k n ik kk ,1 , 0 因若不然,设(z2,z3zn)是上述问题的一个最优解,而(y2,y3yn)不 是它的最优解,由此可见,且c。因此 n i 2 n i iiy v 2 n i iiz w 2 w1y1 n i iiz v 2 v1y1 n i iiy v 1 c n i iiz w 2 w1y1 这说明(y1,z2zn)是所给 0-1 背包问题的一个更优解,从而(y1,y2yn)不 是所给 0-1 背包问题的最优解。此为矛盾1。 递
21、归关系 设所给 0-1 背包问题的子问题 n ik kkx vmax nkix jxw k n ik kk ,1 , 0 的最优值为 m(i,j),即 m(i,j)是背包容量为 j,可选择物品为 i,i+1,n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性 质,可以建立计算 m(i,j)的递归式如下: wjjjim wijviwijimjim 0), 1( ,), 1(),),1(max j)m(i, wnj wnvnj 0 j)m(n, 7 算法描述 基于以上讨论,当 wi(1 i n)为正整数时,用二维数组 m来存储 m(i,j)的相应值,可设计解 0-1 背包问题的动
22、态规划算法 Knapsack 入下: template void Knapsack(Type v,int w,int c,int n,Type* * m) int jMax=min(wn-1,c); for (int j=0;j1;i-) jMax=min(wi-1,c); for (int j=0;j=w1) m1c=max(m1c,m2c-w1+v1); template void Traceback(Type* * m,int w,int c,int n,int x) for (int i=1;i class Knap friend Typep Knapsack(Typep*,Typew
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 背包 问题 算法 研究 实现 本科
链接地址:https://www.31doc.com/p-2083879.html