《数据结构域算法设计-(lecture_09贪心算法090420》由会员分享，可在线阅读，更多相关《数据结构域算法设计-(lecture_09贪心算法090420（31页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计杭州电子科技大学 刘春英 *1这学期，你 了吗？练习Date2每周一星（8）：qzx Date3第九讲 贪心算法 （Greedy Algorithm）Date4导引问题：FatMouse TradeDate5所谓“贪心算法”是指：在对问题求解时，总是作出在当前看来是最好 的选择。也就是说，不从整体上加以考虑，它 所作出的仅仅是在某种意义上的局部最优解（ 是否是全局最优，需要证明）。Date6特别说明：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！Date7用事实说话Date8一、事件序列问题 已知N个事件的发生时刻和结束时刻（见下表，表
2、中事件已按结束时刻升序排序）。一些在时间上没 有重叠的事件，可以构成一个事件序列，如事件 2，8，10。事件序列包含的事件数目，称为该事 件序列的长度。请编程找出一个最长的事件序列。事件编 号0 1 2 3 45678910 11发生时 刻1 3 0 3 256410815 15结束时 刻3 4 7 8 9 10 12 14 15 18 19 20Date9算法分析：n不妨用Begini和Endi表示事件i的开始时刻和 结束时刻。则原题的要求就是找一个最长的序 列a1=M，那么显然用M条长度为1的线段 可以覆盖住所有的区间，所求的线段总长为M 。n如果N=1，那么显然所需线段总长为：n如果N=
3、2，相当于N=1的情况下从某处断开 （从哪儿断开呢？）。n如果N=k呢？Date14三、HDOJ_1050 Moving TablesSample Input3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50 Sample Output10 20 30 Date15算法分析：1、如果没有交叉，总时间应该是多少？2、影响搬运时间的因素是什么？3、如果每趟处理都包含最大重叠，处理 后的效果是什么？4、得出什么结论？Date16附:参考源码(HDOJ- 1050)#include using namespace std; int
4、main() int t,i,j,N,P200;int s,d,temp,k,min; cint; for(i=0;iN; for(j=0;jsd; s=(s-1)/2; d=(d-1)/2; if(sd) temp=s; s=d; d=temp; for(k=s;kmin) min=Pj; coutmin*10endl; return 0; Date17贪心算法的基本步骤 1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一 步时，就根据局部最优策略，得到一个部 分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终 解。Date18贪心算法都很简单吗？看一
5、道难一些的。 （2004年上海赛区：正式赛是简单题）Date19ACM-ICPC Asia Regional, 2004, ShanghaiTian JiThe Horse RacingDate20示意图：928371748795928371748795-200-200-200928371748795-200+200+200Date21谈谈自己的想法吧 Date22Case 1:King: 200 180 160 Tianji: 190 170 150Date23Case 2:King: 200 180 160 Tianji: 180 170 150Date24Case 3:King: 200 180 160 Tianji: 180 155 150Date25总体的思路是什么？Date26提醒：很多贪心类型的题目都象本题一 样，不是最朴素的贪心，而是需 要做一些变化，对于我们，关键 是找到贪心的本质！Date27最后一个思考题Date28Any questions ?Date29相关练习n另外还有n1203、 1204、 1239n1579、 1730、 2285DIY：ACM程序设计在线作业（9） 贪心练习 Date30Welcome to HDOJ Thank You Date31
