ACM课件(lecture-07)贪心算法

ACM程序设计杭州电子科技大学刘春英[e-mail]2020/1/12上一周，你了吗？2020/1/13每周一星（6）：Teddy2020/1/14第七讲贪心算法（GreedyAlgorithm）2020/1/15还记得FatMouse'Trade吗？2020/1/16所谓“贪心算法”是指：在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。2020/1/17特别说明：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！2020/1/18用事实说话——2020/1/19一、事件序列问题已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻34789101214151819202020/1/110算法分析：不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2…an，满足：Begin[a1]End[a1]=…=Begin[an]End[an]可以证明，如果在可能的事件a1a2…an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。（证明：略）2020/1/111思考：请谈谈自己的解题思路2020/1/112思考题2037今年暑假不AC2020/1/113二、区间覆盖问题用i来表示x轴上坐标为[i-1,i]的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=N=50)。例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=3条012345678910112020/1/114算法分析：如果N=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。如果N=1，那么显然所需线段总长为：…如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？）。如果N=k呢？2020/1/115三、HDOJ_1050MovingTablesSampleInput341020304050607080213220031010020803050SampleOutput1020302020/1/116算法分析：1、如果没有交叉，总时间应该是多少？2、影响搬运时间的因素是什么？3、如果每趟处理都包含最大重叠，处理后的效果是什么？4、得出什么结论？2020/1/117附:参考源码(HDOJ-1050)#includeiostreamusingnamespacestd;intmain(){intt,i,j,N,P[200];ints,d,temp,k,min;cint;for(i=0;it;i++){for(j=0;j200;j++)P[j]=0;cinN;for(j=0;jN;j++){cinsd;s=(s-1)/2;d=(d-1)/2;if(sd){temp=s;s=d;d=temp;}for(k=s;k=d;k++)P[k]++;}min=-1;for(j=0;j200;j++)if(P[j]min)min=P[j];coutmin*10endl;}return0;}2020/1/118贪心算法的基本步骤1、从问题的某个初始解出发。2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。3、将所有部分解综合起来，得到问题的最终解。2020/1/119贪心算法都很简单吗？看一道难一些的。（2004年上海赛区：正式赛是简单题）2020/1/120ACM-ICPCAsiaRegional,2004,ShanghaiTianJi—TheHorseRacing2020/1/121示意图：928371748795928371748795-200-200-200928371748795-200+200+2002020/1/122谈谈自己的想法吧～2020/1/123Case1:King:200180160Tianji:1901701502020/1/124Case2:King:200180160Tianji:1801701502020/1/125Case3:King:200180160Tianji:1801551502020/1/126总体的思路是什么？2020/1/127提醒：很多贪心类型的题目都象本题一样，不是最朴素的贪心，而是需要做一些变化，对于我们，关键是找到贪心的本质！2020/1/128最后一个思考题Anyquestions?2020/1/130相关练习1050MovingTables1051WoodenSticks1052TianJi--TheHorseRacing1789DoingHomeworkagain2037今年暑假不AC1045FireNet1053Entropy1054StrategicGame1800FlyingtotheMars2008《ACMProgramming》Exercise(8)_贪心算法2020/1/131下一讲：母函数及其应用2020/1/132WelcometoHDOJThankYou~