没有合适的资源?快使用搜索试试~ 我知道了~
chap16贪心算法1.PDF
需积分: 0 0 下载量 8 浏览量
2022-08-03
18:35:45
上传
评论
收藏 894KB PDF 举报
温馨提示
试读
41页
第一种策略:按价值最大贪心,使目标函 第二种策略:按重量最小贪心,使背包增 第三种策略:按价值率最大贪心,使单位
资源详情
资源评论
资源推荐
算法设计与分析算法设计与分析算法设计与分析算法设计与分析
Design and Analysis of AlgorithmsDesign and Analysis of AlgorithmsDesign and Analysis of AlgorithmsDesign and Analysis of Algorithms
主讲人主讲人
徐徐
云云
主讲人主讲人
徐徐
云云
Fall Fall 2018, 2018, USTCUSTC
Part 1 FoundationPart 1 Foundation
Part 2 Sorting and Order StatisticsPart 2 Sorting and Order Statistics
Part 3 Data StructurePart 3 Data Structure
Part 4 Advanced Design and Analysis TechniquesPart 4 Advanced Design and Analysis Techniques
chap 15 Dynamic Programmingchap 15 Dynamic Programming
chap 16 chap 16 Greedy AlgorithmsGreedy Algorithms
chap 17 Amortized Analysischap 17 Amortized Analysis
Part 5 Advanced Data StructuresPart 5 Advanced Data Structures
Part 6 Graph AlgorithmsPart 6 Graph Algorithms
Part 7 Selected TopicsPart 7 Selected Topics
Part 8 SupplementPart 8 Supplement
第第1616章章 贪心算法贪心算法
16.1 16.1 方法概述方法概述
16.2 16.2
小数背包小数背包
16.2 16.2
小数背包小数背包
16.3 16.3 活动安排活动安排
16 4 16 4
最优装载最优装载
16
.
4 16
.
4
最优装载最优装载
16.5 16.5 找钱问题找钱问题
16.1 方法概述
基本思想
基本思想
求解步骤
求
适合
求
解问题的特征
存在的问题
存在的问题
与动态规划法的比较
示例
2018/10/9
算法设计与分析
4
基本思想
从问题的某一个初始解出发,通过一系列的贪
心选择
——
当前状态下的
局部最优
选择
,
逐步
心选择
当前状态下的
局部最优
选择
,
逐步
逼近给定的目标,尽可能快地求得更好的解。
在贪心算法
(
greedy method
)
中也采用逐步构
在贪心算法
(
greedy method
)
中也采用逐步构
造最优解的方法。在每个阶段,都作出一个按
某个评价
函数
最
优的决
策
,该
评价
函数
最
优
策
某个评价 最 策
评价 最 策
略称为贪心准则(greedy criterion)。
贪心
算
法的正确
性
,就
是要
证
明
按贪心
准则求
算性
是要 明 准则求
得的解是全局最优解。
贪心
算
法不能
对
所
有问题都得
到全局最优
解
。
算 对 有问题都得 解
但对许多问题它能产生全局最优解,如单源最
短路经问题,最小生成树问题等。
2018/10/9
算法设计与分析
5
剩余40页未读,继续阅读
嗨了伐得了
- 粉丝: 18
- 资源: 290
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0