ACM课件 1 lecture_06 贪心算法.ppt

《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的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1

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/202

8、123谈谈自己的想法——8/4/202124Case1:King:200180160Tianji:1901701508/4/202125Case2:K