欢迎来到天天文库
浏览记录
ID:56964600
大小:398.00 KB
页数:44页
时间:2020-07-22
《贪心算法入门课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、ACM程序设计计算机学院9/4/20211调课三周(11/6,11/13,11/20)9/4/20212今天,你了吗?AC9/4/20213每周一星(5):枫冰叶子9/4/20214第六讲贪心算法(GreedyAlgorithm)9/4/20215还记得hdoj_1009吗?FatMouse'Trade9/4/20216所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。9/4/20217特别说明:若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思
2、想在该问题的应用结果就是最优解!!9/4/20218用事实说话——9/4/20219实例分析9/4/202110一、事件序列问题已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{2,8,10}。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻34789101214151819209/4/202111算法分析:不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题
3、的要求就是找一个最长的序列a14、可以任意长,但是要求所画线段之和最小,并且线段的数目不超过N(1==M,那么显然用M条长度为1的线段可以覆盖住所有的区间,所求的线段总长为M。如果N=1,那么显然所需线段总长为:…如果N=2,相当于N=1的情况下从某处断开(从哪儿断开呢?)。如果N=k呢?9/4/202116三、HDOJ_1050MovingTables题目链接SampleInput34102030405060708021322005、31010020803050SampleOutput1020309/4/202117算法分析:1、如果没有交叉,总时间应该是多少?2、影响搬运时间的因素是什么?3、如果每趟处理都包含最大重叠,处理后的效果是什么?4、得出什么结论?9/4/202118HDOJ_1050源码:#includeusingnamespacestd;intmain(){intt,i,j,N,P[200];ints,d,temp,k,min;cin>>t;for(i=0;i>N;for(j=0;6、j>s>>d;s=(s-1)/2;d=(d-1)/2;if(s>d){temp=s;s=d;d=temp;}for(k=s;k<=d;k++)P[k]++;}min=-1;for(j=0;j<200;j++)if(P[j]>min)min=P[j];cout<7、很简单吗?看一道难一些的。(2004年上海赛区试题:当时算是简单题)9/4/202121ACM-ICPCAsiaRegional,2004,ShanghaiProblemHTianJi—TheHorseRacing9/4/202122示意图:928371748795928371748795-200-200-200928371748795-200+200+2009/4/202123谈谈自己的想法——9/4/202124Case1:King:200180160Tianji:1901701509/4/202125Case2:King:2001
4、可以任意长,但是要求所画线段之和最小,并且线段的数目不超过N(1==M,那么显然用M条长度为1的线段可以覆盖住所有的区间,所求的线段总长为M。如果N=1,那么显然所需线段总长为:…如果N=2,相当于N=1的情况下从某处断开(从哪儿断开呢?)。如果N=k呢?9/4/202116三、HDOJ_1050MovingTables题目链接SampleInput3410203040506070802132200
5、31010020803050SampleOutput1020309/4/202117算法分析:1、如果没有交叉,总时间应该是多少?2、影响搬运时间的因素是什么?3、如果每趟处理都包含最大重叠,处理后的效果是什么?4、得出什么结论?9/4/202118HDOJ_1050源码:#includeusingnamespacestd;intmain(){intt,i,j,N,P[200];ints,d,temp,k,min;cin>>t;for(i=0;i>N;for(j=0;
6、j>s>>d;s=(s-1)/2;d=(d-1)/2;if(s>d){temp=s;s=d;d=temp;}for(k=s;k<=d;k++)P[k]++;}min=-1;for(j=0;j<200;j++)if(P[j]>min)min=P[j];cout<7、很简单吗?看一道难一些的。(2004年上海赛区试题:当时算是简单题)9/4/202121ACM-ICPCAsiaRegional,2004,ShanghaiProblemHTianJi—TheHorseRacing9/4/202122示意图:928371748795928371748795-200-200-200928371748795-200+200+2009/4/202123谈谈自己的想法——9/4/202124Case1:King:200180160Tianji:1901701509/4/202125Case2:King:2001
7、很简单吗?看一道难一些的。(2004年上海赛区试题:当时算是简单题)9/4/202121ACM-ICPCAsiaRegional,2004,ShanghaiProblemHTianJi—TheHorseRacing9/4/202122示意图:928371748795928371748795-200-200-200928371748795-200+200+2009/4/202123谈谈自己的想法——9/4/202124Case1:King:200180160Tianji:1901701509/4/202125Case2:King:2001
此文档下载收益归作者所有