欢迎来到天天文库
浏览记录
ID:44186256
大小:500.50 KB
页数:44页
时间:2019-10-19
《(lecture_06)贪心算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、ACM程序设计计算机学院刘春英9/9/20211调课三周(11/6,11/13,11/20)9/9/20212今天,你了吗?AC9/9/20213每周一星(5):枫冰叶子9/9/20214第六讲贪心算法(GreedyAlgorithm)9/9/20215还记得hdoj_1009吗?FatMouse'Trade9/9/20216所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。9/9/20217特别说明:若要用
2、贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!9/9/20218用事实说话——9/9/20219实例分析9/9/202110一、事件序列问题已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{2,8,10}。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻34789101214151819209/9/2
3、02111算法分析:不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a14、]的区间(长度为1),并给出M(1==M,那么显然用M条长度为1的线段可以覆盖住所有的区间,所求的线段总长为M。如果N=1,那么显然所需线段总长为:…如果N=2,相当于N=1的情况下从某处断开(从哪儿断开呢?5、)。如果N=k呢?9/9/202116三、HDOJ_1050MovingTables题目链接SampleInput341020304050607080213220031010020803050SampleOutput1020309/9/202117算法分析:1、如果没有交叉,总时间应该是多少?2、影响搬运时间的因素是什么?3、如果每趟处理都包含最大重叠,处理后的效果是什么?4、得出什么结论?9/9/202118HDOJ_1050源码:#includeusingnamespaces6、td;intmain(){intt,i,j,N,P[200];ints,d,temp,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、dl;}return0;}9/9/202119贪心算法的基本步骤1、从问题的某个初始解出发。2、采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。3、将所有部分解综合起来,得到问题的最终解。9/9/202120贪心算法都很简单吗?看一道难一些的。(2004年上海赛区试题:当时算是简单题)9/9/202121ACM-ICPCAsiaRegional,2004,ShanghaiProblemHTianJi—TheHorseRacing9/9/202122示意图:9283717488、795928371748795-200-200-200928371748795-200+200+2009/9/202123谈谈自己的想法——9/9/202124Case1:King:200180160Tianji:1901701509/9/202125Case2:King:2
4、]的区间(长度为1),并给出M(1==M,那么显然用M条长度为1的线段可以覆盖住所有的区间,所求的线段总长为M。如果N=1,那么显然所需线段总长为:…如果N=2,相当于N=1的情况下从某处断开(从哪儿断开呢?
5、)。如果N=k呢?9/9/202116三、HDOJ_1050MovingTables题目链接SampleInput341020304050607080213220031010020803050SampleOutput1020309/9/202117算法分析:1、如果没有交叉,总时间应该是多少?2、影响搬运时间的因素是什么?3、如果每趟处理都包含最大重叠,处理后的效果是什么?4、得出什么结论?9/9/202118HDOJ_1050源码:#includeusingnamespaces
6、td;intmain(){intt,i,j,N,P[200];ints,d,temp,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、dl;}return0;}9/9/202119贪心算法的基本步骤1、从问题的某个初始解出发。2、采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。3、将所有部分解综合起来,得到问题的最终解。9/9/202120贪心算法都很简单吗?看一道难一些的。(2004年上海赛区试题:当时算是简单题)9/9/202121ACM-ICPCAsiaRegional,2004,ShanghaiProblemHTianJi—TheHorseRacing9/9/202122示意图:9283717488、795928371748795-200-200-200928371748795-200+200+2009/9/202123谈谈自己的想法——9/9/202124Case1:King:200180160Tianji:1901701509/9/202125Case2:King:2
7、dl;}return0;}9/9/202119贪心算法的基本步骤1、从问题的某个初始解出发。2、采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。3、将所有部分解综合起来,得到问题的最终解。9/9/202120贪心算法都很简单吗?看一道难一些的。(2004年上海赛区试题:当时算是简单题)9/9/202121ACM-ICPCAsiaRegional,2004,ShanghaiProblemHTianJi—TheHorseRacing9/9/202122示意图:928371748
8、795928371748795-200-200-200928371748795-200+200+2009/9/202123谈谈自己的想法——9/9/202124Case1:King:200180160Tianji:1901701509/9/202125Case2:King:2
此文档下载收益归作者所有