有哪些信誉好的足球投注网站- 1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
- 2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 4、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 5、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 6、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 7、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
解0-1背包问题的算法比较
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
课 程 设 计
课程名称 算法分析与设计
题目名称 0-1背包问题的算法对比
学生学院 计算机学院
专业班级
学 号
学生姓名
指导教师
2014 年5 月
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
目 录
1 0-1 背包问题介绍 1
1.1 问题由来 1
1.2 问题描述 1
2 分支限界法 1
2.1 求解目标 1
2.2 基本思想 2
2.3 两种不同分支限界法 2
3 分支限界法解0-1背包问题 4
3.1 算法思想 4
3.2 算法实现 5
4 异同对比 6
4.1 与回溯法对比 6
4.1.1 回溯法算法思想 6
4.1.2 问题的解空间 7
4.1.3 求解步骤 7
4.1.4 算法描述 8
4.1.5 异同之处 10
4.2 与动态规划对比 10
4.2.1 动态规划算法基本思想 10
4.2.2 求解步骤11
4.2.3 0-1 背包问题的递归关系11
4.2.4 算法描述 12
4.2.5 差异对比 14
参考文献15
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
0-1 背包问题的算法对比
1 0-1 背包问题介绍
1.1 问题由来
0-1 背包问题是从子集中选取最优解的问题，最早由Dantzing 于20 世纪50 年
代首次提出，现已成为计算机学科中一个经典的NP 完全难题。它在很多领域有广
泛的应用，很多实际问题都可转换为0-1 背包问题，因此有效解决0-1 背包问题具
有重要意义。由于0-1 背包的解空间树是一棵子集树, 而所要求的解要有最优解性
质，故0-1 背包问题满足动态规划、回溯法和分支限界法的求解条件。
1.2 问题描述
给定n 种物品和一个背包。物品i 的重量为 ，其价值为 ，背包的容量为 。
i i c
问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入
背包
文档评论（0）