ACM课件贪心算法
ACM程序设计,杭州电子科技大学 刘春英 ,2020/8/16,2,上一周，,你 了吗？,练习,2020/8/16,3,每周一星（6）：,Teddy,2020/8/16,4,第七讲,贪心算法（Greedy Algorithm）,2020/8/16,5,还记得FatMouse Trade吗？,2020/8/16,6,所谓“贪心算法”是指：,在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。,2020/8/16,7,特别说明：,若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！,2020/8/16,8,用事实说话,2020/8/16,9,一、事件序列问题,已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件 2，8，10。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。,2020/8/16,10,算法分析：,不妨用Begini和Endi表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1<a2<<an，满足： Begina1<Enda1<=<= Beginan<Endan,可以证明，如果在可能的事件a1<a2<<an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。 （证明：略）,2020/8/16,11,思考：,请谈谈自己的解题思路,2020/8/16,12,思考题,2037 今年暑假不AC,2020/8/16,13,二、区间覆盖问题,用i来表示x轴上坐标为i-1,i的区间（长度为1），并给出M(1=<M=<200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=<N=<50)。 例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=3条 0 1 2 3 4 5 6 7 8 9 10 11,2020/8/16,14,算法分析：,如果N=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。 如果N=1，那么显然所需线段总长为： 如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？）。 如果N=k呢？,2020/8/16,15,三、HDOJ_1050 Moving Tables,Sample Input 3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50,Sample Output 10 20 30,2020/8/16,16,算法分析：,1、如果没有交叉，总时间应该是多少？ 2、影响搬运时间的因素是什么？ 3、如果每趟处理都包含最大重叠，处理后的效果是什么？ 4、得出什么结论？,2020/8/16,17,附:参考源码(HDOJ-1050),#include using namespace std; int main() int t,i,j,N,P200; int s,d,temp,k,min; cint; for(i=0;iN; for(j=0;jsd; s=(s-1)/2; d=(d-1)/2;,if(sd) temp=s; s=d; d=temp; for(k=s;kmin) min=Pj; cout<<min*10<<endl; return 0; ,2020/8/16,18,贪心算法的基本步骤,1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。,2020/8/16,19,贪心算法都很简单吗？,看一道难一些的。 （2004年上海赛区：正式赛是简单题）,2020/8/16,20,ACM-ICPC Asia Regional, 2004, Shanghai,Tian JiThe Horse Racing,2020/8/16,21,示意图：,2020/8/16,22,谈谈自己的想法吧,2020/8/16,23,Case 1:,King: 200 180 160 Tianji: 190 170 150,2020/8/16,24,Case 2:,King: 200 180 160 Tianji: 180 170 150,2020/8/16,25,Case 3:,King: 200 180 160 Tianji: 180 155 150,2020/8/16,26,总体的思路是什么？,2020/8/16,27,提醒：,很多贪心类型的题目都象本题一样，不是最朴素的贪心，而是需要做一些变化，对于我们，关键是找到贪心的本质！,2020/8/16,28,最后一个思考题,Any questions?,2020/8/16,30,相关练习,1050Moving Tables 1051Wooden Sticks 1052Tian Ji - The Horse Racing 1789 Doing Homework again 2037 今年暑假不AC 1045Fire Net 1053Entropy 1054Strategic Game 1800 Flying to the Mars 1042, 1065, 1230, 1323, 1477, 1716, 1784,1328 1755（或用单纯形方法），2054，1017， 1328，1862， 1922 ，2054， 2209， 2313，,2008ACM ProgrammingExercise(8)_贪心算法,2020/8/16,31,下一讲：,母函数及其应用,2020/8/16,32,Welcome to HDOJ,Thank You ,
