一个问题的最优解，所做的每一次选择都是当前状态下的贪 心选择，通过一系列的选择来得到最终解。这种策略是一种 很简洁的方法，适用于许多问题，但并不能依赖于它，因为 它还有一下不足：
（1）不能保证求得的最后解是最佳的，由于贪
心策略总 是从局部看来是最优的选择，因此从整 体上考虑并不一定是最优解；
（2）贪心算法只能用来求某些最大或最小解的 问题；
（3）贪心算法只能确定某些问题的可行性范围
。
因此，贪心算法具有局限性，并不是总能得到最优
解。 07.04.2020
16
谢谢观 看！！！
07.04.2020
17
感谢亲观看此幻灯片，此课件部分内容来源于网络， 如有侵权请及时联系我们删除，谢谢配合！
采用最长处理时间作业优先的贪心选择策略可以设计出解 多机调度问题的较好的近似算法。
07.04.2020
14
12
‫ﻻ‬常见应用
3、排队问题
在一个医院B 超室，有n个人要做不同身体部位的B超， 已知每个人需要处理的时间为ti，（0<i<=n）,请求出一种排 列次序，使每个人排队等候时间总和最小。 本题贪心算法：
07.04.2020
3
‫ﻻ‬算法思想
在现实生活中，我们 经常为下意识的做贪心的 选择，例如在购买商品时 候总是寻求物美价廉的物 品，在质量相同情况下， 价格低的首选。
07.04.2020
4
‫ﻻ‬算法思想
将问题的求解过程看作是一系列选择，每 次选择一个输入，每次选择都是当前状态下的 最好选择(局部最优解)。每作一次选择后，所 求问题会简化为一个规模更小的子问题。从而 通过每一步的最优解逐步达到整体的最优解。
解：如果用贪心法，每次向最大的方向 走 ，得到结果为1+6+8+2+3=20。可是明明 还有另一条路，1+3+6+6+7=23。
1 63 826骤会有 影响！第三级选了8，就选不到第四、五 级较大的数了。
32476
07.04.2020
15
综述
贪心算法是一种分级处理方法，它得到某种度量意义下
从问题的某一初始解出发； while 能朝给定总目标前进一 步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个
可行解；
真正意义要求解原问题
将原问题变成更小 子问题的步骤
理解
07.04.2020
7
‫ﻻ‬算法过程
【贪心算法一般步骤】
1、设计数据找规律
2、进行贪心猜想
} 3、正确性证明（严格证明和一般证明） ·严格证明：数学归纳和反证法 ·一般证明：列举反例
07.04.2020
5
‫ﻻ‬算法过程
顾名思义，贪心算法总是作出在当前看来最 好的选择。也就是说贪心算法并不从整体最优考 虑，它所作出的选择只是在某种意义上的局部最 优选择。
【标准转化】 贪心猜想（贪心策略）
找硬币的时候：
找的硬币总数最少→使剩余金额最少
07.04.2020
原
现
6
‫ﻻ‬算法过程
[贪心算法步骤]
不相交 , 则称活动 i 与 j 是 相容 的 . 求解目标是在所给的活动集合 中选出最大相容活动子集. 【算法思路】将n个活动按结束时间非减序排列,依次考虑活动i, 若i 与已选择的活动相容,则添加此活动到相容活动子集. 【例】设待安排的11个活动起止时间按结束时间的非减序排列
07.04.2020
贪心算法详解与应用举例
07.04.2020
班级：软件12-1 组长：孟洁 组员：王明桃 赵强
1
※详解： 算法思想 算法过程 算法分析
※应用举例：
常见应用
07.04.2020
2
‫ﻻ‬算法思想
引例——找零钱
找钱的方法： 25+25+10+5+1+1
我们有种直觉的倾向：
在找零钱时，直觉 告诉我们使用面值大的硬 币，剩余的金额就越少。
若无法证 明，此证 明可省
4、程序实现
07.04.2020
8
‫ﻻ‬算法分析
【适用问题】
具备贪心选择和最优子结构性质的最
优化问题
整体的最优解可通过一系列 局部最优解达到. 每次的选择 可以依赖以前作出的选择, 但 不能依赖于后面的选择
问题的整体最优解 中包含着它子问题 的最优解
【常见应用】背包问题,最小生成树,最短路径,作业调度等等
【算法优点】求解速度快,时间复杂性有较低的阶.
【算法缺点】需证明是最优解.
07.04.2020
9
‫ﻻ‬常见应用
1、活动安排问题
【问题陈述】设有n个活动E={1,2,…,n}要使用同一资源,同一时间内 只允许一个活动使用该资源. 设活动i的起止时间区间[si, fi) ,如果选
择了活动i,则它在时间区间[si, fi)内占用该资源;若[si, fi)与[sJ, fJ)
n个人时间从小到大排序，就是这n个人最佳排队方案 。求部分和的和即为所求。
07.04.2020
13
谈谈自己的 想法——
07.04.2020
14
选择需慎重
贪心算法在对问题求解时，总是作出在当前看 来是最好的选择。也就是说，不从整体上加以考虑 ，它所作出的仅仅是在某种意义上的局部最优解。
eg：数字三角形问题：有一个数字三角形 （如下图）。现有一只蚂蚁从顶层开始 向下走，每走下一级时，可向左下方向 或右下方向走。求走到底层后它所经 过 的数的最大值。
10
‫ﻻ‬常见应用
活动安排问题贪心算法： void GreedySelector(int n, Type s[], Type f[], bool A[]) {
A[1]=true; int j=1; for (int i=2;i<=n;i++) {
if (s[i]>=f[j]) { A[i]=true; j=i; }
else A[i]=false; } }
07.04.2020
11
‫ﻻ‬常见应用
2、多机调度问题
多机调度问题要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。
约定，每个作业均可在任何一台机器上加工处理，但未完 工前不允许中断处理。作业不能拆分成更小的子作业。
例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工 处理。各作业所需时间为{2,14,4,16,6,5,3}。按算法greedy产生的作 业调度如下图所示，所需的加工时间为17。