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