贪心算法-acm.ppt

贪心算法
主讲人：张云聪
目录
什么是贪心算法
1
贪心算法典型例题
2
一些细节琐事
3
推荐题目
4
什么是贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的一般性质
能够使用贪心算法的问题必须满足下面的两个性质：
；
，并且这些局部都能够求出最优解。
NYOJ-6 喷水装置（一）
现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。
解题思路
这个题目思路很容易想，肯定是优先使用半径大的喷水装置。因为半径越大的喷水装置所能覆盖的范围就越大。
其实这个确定优先选择哪一个的过程就是贪心选择的过程。
所以本题就是先对所有的喷水装置半径排序，计算出，每个喷水装置所能覆盖的长度。每次都选出当前半径最大的，直到能覆盖完所有的草地。
NYOJ-14 活动安排问题
学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，小礼堂只有上午，下午和晚上三个时间段能安排活动，每个时间段最多安排一个活动，每个活动可能占用多个时间段。为了方便，小刘按时间表顺序把所有时间段分别编号为1,2,3,4…，现在给你一些活动计划的时间表，小刘想尽可能的安排更多的活动，请问他该如何安排。
如：活动1：3号时间段到10号时间段（包括10号时间段，下同）
活动2：4号时间段到6号时间段
活动3：7号时间段到15号时间段
活动4：1号时间段到5号时间段
活动5：2号时间段到3号时间段
小刘应该选择：活动2，活动3，活动5
思考
做这道题目的时候，我们先来想一下下面的情况：如果有两个活动让你选择一个，它们的结束时间一前一后，那么，我们应该选择哪一个才能有利于之后选取更多的活动呢？
思考
经过思索，我们发现，在只有两个我们应该选择的是结束时间较早的那个活动。
推广
同样，在有一大堆活动时，我们最先应该选择结束时间最早的那个，以利于之后能安排更多的活动，然后，再在剩下的可选的会场中选择最可能结束时间最早的那个，依次类推，直到无法安排任何活动为止。
也就是说，每次选择时，都应该贪婪的选择结束时间最短的那个活动。