NOIP基础算法——贪心和分治pascal课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,NOIP,基础算法,分治与贪心,巴蜀中学 黄新军,1,第五部分 分治策略,2,一、分治思想,分治,(divide-and-conquer),就是,“,分而治之,”,的意思，其实质就是将原问题分成,n,个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。,3,二、分治法的适用条件,能使用分治法解决的问题，它们一般具备以下几个特征：,该问题可以分解成若干相互独立、规模较小的相同子问题子问题缩小到一定的程度就能轻易得到解；,子问题的解合并后，能得到原问题的解；,分治法在信息学竞赛中应用非常广泛，使用分治策略能生成一些常用的算法和数据结构，如快排、最优二叉树、线段树等；还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。,4,三、分治的三步骤,分解：,将要解决的问题分解成若干个规模较小的同类子问题；,解决：当,子问题划分得足够小时，求解出子问题的解。,合并：,将子问题的解逐层合并成原问题的解。,5,分治算法设计过程图,6,由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。,要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成,K,个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当,n,6,时，等分定量成两个规模为,3,的子表,L1,和,L2,不是最佳分割。一般来讲，都是,2,分为主。,7,四、分治的框架结构,procedure DIVIDE(),begin,if(,问题不可分,)then/,解决,begin,直接求解；,返回问题的解；,end,else begin,对原问题进行分治；,/,分解,递归对每一个分治的部分求解,;,归并整个问题，得出全问题的解,;/,合并,end,end;,8,五、分治的典型应用,1,、求最大值和最小值,2,、非线性方程求根,3,、二分查找,4,、归并排序,5,、快速幂,6,、求解线性递推关系,7,、棋盘覆盖问题,8,、循环日程表问题,9,、寻找最近点对,9,1,、求最大值和最小值,例题,1,：给,n,个实数，求它们之中最大值和最小值，要求比较次数尽量小。,分析：,假设数据个数为,n,存放在数组,a1.n,中。可以直接进行比较：,minn:=a1;maxx:=a1;,for i:=2 to n do,if aimaxx then maxx:=ai;,else if aixr1 then begin maxx:xr2;minn:=xr1;end,else begin maxx:=xr1;minn:=xr2;end,end,else begin,d:=(r1+r2)/2;,pd(r1,d,max1,min1);,pd(d+1,r2,max2,min2);,if max1max2 then maxx:=max1;else maxx:=max2;,if min1=1,。要求由小到大依次在同一行输出这三个实根,(,根与根之间留有空格,),，并精确到小数点后,4,位。,【,文件输入,】,输入仅一行，有四个数，依次为,a,、,b,、,c,、,d,【,文件输出,】,输出也只有一行，即三个根,(,从小到大输出,)样例输入,】,1-5-4 20,【,样例输入,】,-2.00 2.00 5.00,13,分析,如果精确到小数点后两位，可用简单枚举法：将,x,从,-100.00,到,100.00,（步长,0.01,）逐一枚举，得到,20000,个,f(x),，取其值与,0,最接近的三个,f(x),，对应的,x,即为答案。而题目已改成精度为小数点后,4,位，枚举算法时间复杂度将达不到要求。,直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值,14,分析,A.,当已知区间,(a,b),内有一个根时；,用二分法求根，若区间,(a,b),内有根，则必有,f(a)*f(b)b,或,f(a+b)/2)=0,，则可确定根为,(a+b)/2,并退出过程；,(2).,若,f(a)*f(a+b)/2)0,则必然有,f(a+b)/2)*f(b)=1,。因此可知：在,-100,-99,、,-99,-98,、,、,99,，,100,、,100,，,100,这,201,个区间内，每个区间内至多只能有一个根。即：除区间,100,，,100,外，其余区间,a,a+1,，只有当,f(a)=0,或,f(a),f(a+1)0,时，方程在此区间内才有解。若,f(a)=0,，解即为,a,；若,f(a),f(a+1)0,，则可以利用,A,中所述的二分法迅速出找出解。如此可求出方程的所有的解。,16,核心参考代码,procedure divide(x1,x2:double),Begin,var x0,y0,y1,y2:,double,;,x0:=(x1+x2)div 2;,y1:=cal(x1);y2:=cal(x2);y0:=cal(x0);,if(x2-x10.00001 and y1*y20)then,begin write(x2+x1)div 2:0:4);exit;end,if(y1*y01)then divide(x1,x0);,if(y0*y21)then divide(x0,x2);,End;,17,3,、归并排序,归并排序的基本思想：,归并排序充分应用分治算法的策略，通过二分的思想，将,n,个数最终分成,n,个单独的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说，,归并过程,为：,（,1,）划分：,把序列分成元素个数相等的两半；,（,2,）递归求解：,把两半分别排序；,（,3,）合并：,把两个有序表合成一个有序表；,18,19,分析,显然，前两部分是很容易完成的，,关键在于如何把两个有序表合成一个,。每次只需要把两个序列中当前的最小元素加以比较，删除较小元素并加入合并后的新表。,20,核心参考代码,procedure MergeSort(left,right:integer)/,归并排序,begin,if left=right then exit;/,只有一个元素,mid:=(left+right)div 2;/,找中间位,MergeSort(left,mid);/,对左边归并,MergeSort(mid+1,right);/,对右边归并,i:=left;j:=mid+1,p:=left;/,合并左右,while(i=mid and jaj)then begin tempp:=aj;inc(p);inc(j);end,else begin tempp:=ai;inc(p);inc(i);end,while(i=mid)do begin tempp:=ai;inc(p);inc(i);end,while(j=right)do begin tempp:=aj;inc(p);inc(i);end,for i:=left to right do ai:=tempi;,End;,21,【,变形,1】,逆序对数目,例题,3,：求,“,逆序对,”,。,给定一整数数组,A=(A1,A2,An),若,iAj,则,就为一个逆序对。例如数组（,3,，,1,，,4,，,5,，,2,）的逆序对有,。问题是，输入,n,和,A,数组，统计逆序对数目。,数据范围：,1=naj then c:=c+1;,时间效率不尽如人意,.,问题出现在哪里呢？,23,分治算法采用二分法求解,:,记数列,ast,ed,的逆序对数目为,d(st,ed);,mid=(st+ed)/2,则有：,d(st,ed)=d(st,mid)+d(mid+1,ed)+F(st,mid,ed),其中,F(st,mid,ed),表示一个数取自,ast,mid,令一个数取自,amid+1,ed,的逆序对数目。,24,和归并排序一样，划分和递归求解都好办，关键在于合并：如何求出,i,在左边，而,j,在右边的逆序对数目呢？统计的常见技巧是,“,分类,”,。我们按照,j,的不同把这些,“,跨越两边,”,的逆序对进行分类：只要对于右边的每个,j,，统计左边比它大的元素个数,f(j),，则所有,f(j),之和便是答案。,幸运的是，归并排序可以帮助我们,“,顺便,”,完成,f(j),的计算：由于合并操作是从小到大进行排序的，当右边的,aj,复制到,T,中时，左边还没有来得及复制到,T,的那些数就是左边所有比,aj,大的数。此时累加器中加上左边元素个数,mid-i+1,即可。,即把,“,if(aiaj)then begin tempp:=aj;inc(p);inc(j);end,改为,“,if(aiaj)then,begin,tot:=tot+mid-i+1;,tempp:=aj;inc(p);inc(j);end,25,4,、二分查找,【,问题描述,】,给出从小到大排列的,n,个不同数a1an,，试判断元素,x,是否出现在表中。,方法,1,：顺序查找。,方法是一个个寻找，时间复杂度为,O(n),。这个方法并没有用到,“,n,个数从小到大排列,”,这一个关键条件，因而时间效率低下。,26,方法,2,：二分查找,只需要比较,log,2,n,个元素。假设需要在,aLar,中查找元素,x,。,划分：,检查某个元素,am(L=mx,，那么元素只可能在,aLam-1,中；,如果,amr exit(-1);,m:=(L+r)div 2;,if am=x bsh:=m;,else if amx then bsh:=bsh(L,m-1,x);,else bsh:=bsh(m+1,r,x);End;,28,方法,2,：二分查找的非递归实现：,function bsh(L,r,x:integer):integer;,Begin,var m:integer;,while(Lx then r:=m-1,else L:=m+1;,end,bsh:=-1;/,查找不成功,End;,29,【,扩展,1】,二分查找求下界，即第一次出现的位置,function Erfen(L,r,x:integer):integer;,begin,var mid:integer;,while(Lr)do,begin,mid:=(L+r)div 2;,if x=amid then r:=mid,else L:=mid+1;,end;,Erfen:=L;,end;,【,扩展,2】,二分查找求上界，即最后一次出现位置的后一个位置,30,例题：奇怪的函数,【,问题描述,】,使得,x,x,达到或超过,n,位数字的最小正整数,x,是多少？,【,文件输入,】,输入一个正整数,n,。,【,文件输出,】,输出使得,x,x,达到,n,位数字的最小正整数,x,。,31,【,变形,】,查找等值点,【,问题描述,】,n,个不同整数从小到大排序后放在数组,A,1,A,n,中，是否存在,i,，使得,A,i,=i,？若存在，试找到此点。,32,33,5,、快速幂,【,问题描述,】,计算,a,n,%k,，,n2),，其中,f1=1f2=1,。现在请你求,Fibonacci,数列的第,n,项。,【,文件输入,】,输入文件只有一行为一个整数,n(1=n=231-1),。,【,文件输出,】,输出文件只有一行为一个整数，表示,Fibonacci,数列的第,n,项,mod 32768,的值。,【,样例输入,】,4,【,样例输出,】,3,【,数据范围,】,对于,20%,的数据，,1=n=1000,对于,40%,的数据，,1=n=10000000,对于,100%,的数据，,1=n=231-1,38,朴素算法，肯定超时,procedure Fib(n:integer),Begin,var i:integer;,f0:=0;f1:=1for i:=2 to n do fi:=fi-1+fi-2;,End;,先复习矩阵乘法,两个,2*2,矩阵相乘的公式为,39,可用倍增法在,O(logn),时间内求出幂,(,忽略高精度,),40,扩展练习：,若,fi=fi-1+fi-2+fi-3,，如何计算求出,fn,41,7,、棋盘覆盖问题,42,分析,43,8,、循环日程表问题,【,例题,】,比赛安排,【,问题描述,】,设有,2,n,(n=6),个球队进行单循环比赛,计划在,2,n,-1,天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在,2,n,-1,天内每个队都与不同的对手比赛。例如,n=2,时的比赛安排为：队,1 2 3 4,比赛,1-2 3-4,第一天,1-3 2-4,第二天,1-4 2-3,第三天,【,文件输入,】,一个整数,n,。,【,文件输出,】,输出比赛安排表。,【,样例输入,】2,【,样例输出,】,1-2 3-4 1-3 2-4 1-4 2-3,44,初看此题，感觉无法下手，因为没有任何直接可用的算法和数据结构。,仔细分析，可以发现，将问题进行分解，能找出规律。,当,n=1,时，共有,2,个球队参赛，一天就可以比完。,当,n=2,时，共有,4,个球队，需比赛,3,天。从,2,个球队的比赛安排表中可以看出，左上角与右下角对称，左下角与右上角对称，左下角的值是由左上角值加,n,得到的。,45,read(n);,m:=1;a1,1:=1;h:=1;,for i:=1 to n do m=2*m;/,比赛总队数,while(h=m)do /,从一个球队开始构造,begin,for i:=1 to h do/,构造其余三个方阵,for j:=1 to h do,begin,ai,j+h:=ai,j+h;/,构造右上角方阵,ai+h,j:=ai,j+h;/,构造左下角方阵,ai+h,j+h:=ai,j;/,构造右下角方阵,end;,h:=h*2;,end;,核心参考代码,46,9,、寻找最近点对,给定平面上,n,个点,找出其中的一对点的距离,使得在这,n,个点的所有点对中,该距离为所有点对中最小的。（,n=60000,）,47,分析,【,问题简述,】,给定平面上,n,个点的坐标，找出其中欧几里德距离最近的两个点。,【,方法,1】,枚举算法。,需要枚举,O(n,2,),个点对，每个距离的计算时间为,O(1),，故总的时间复杂度为,O(n,2,),。,有没有更好的算法呢？,48,【,方法,2】,分治算法,先按照,X,坐标排序，把所有点划分成个数尽量相等的两部分，分别求最近点对，设距离分别为,dL,和,dr,。,49,合并：令,d=mindL,dr,，则跨越两边的点对中，只有下面的竖条中的才有可能更近。,需要检查竖条里的所有点对吗？,50,由,d,的意义可知，,P2,中任何,2,个,S,中的点的距离都不小于,d,。由此而来可以推出矩形,R,中最多只有,6,个,d/2*2/3*d,的矩形,(,如下图所示,),。,51,（反证法）若矩形,R,中有多于,6,个,S,中的点，则由鸽笼原理易知至少有一个,d/2*2/3*d,的小矩形中有,2,个以上,S,中的点。设,U,，,V,是这样,2,个点，它们位于同一小矩形中，则：,(X(U)-X(V),2,+(Y(U)-Y(V),2,=(d/2),2,+(d/2),2,=25d,2,/36,因此，,D(U,V)=5d/6d,。这与,d,的意义相矛盾。也就是说矩形,R,中最多只有,6,个,S,中的点。,由于这种稀疏性质，对于,P1,中任一点,p,，P2,中最多只有,6,个点与它构成最接近点对的候选者。,52,总结归纳,分治是一种解题的策略，它的基本思想是：,“,如果整个问题比较复杂，可以将问题分化，各个击破。,”,分治包含,“,分,”,和,“,治,”,两层含义，如何分，分后如何,“,治,”,成为解决问题的关键所在,不是所有的问题都可以采用分治，只有那些能将问题分成与原问题类似的子问题，并且归并后符合原问题的性质的问题，才能进行分治,分治可进行二分，三分等等，具体怎么分，需看问题的性质和分治后的效果。,只有深刻地领会分治的思想，认真分析分治后可能产生的预期效率，才能灵活地运用分治思想解决实际问题。,53,第六部分 贪心策略,54,贪心方法的基本思想,贪心是一种解题策略，也是一种解题思想,使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优,利用贪心策略解题，需要解决两个问题：,该题是否适合于用贪心策略求解,如何选择贪心标准，以得到问题的最优解,55,【,引例,】,在一个,NM,的方格阵中，每一格子赋予一个数（即为权），规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。,我们以,23,的矩阵为例：,若按,贪心策略,求解，所得路径为：,1346,；,若按,动态规划,求解，所得路径为：,12106,。,56,贪心法的特点,1.,贪心选择性质：,算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。,2.,最优子结构性质：,算法中每一次都取得了最优解,(,即局部最优解,),，要保证最后的结果最优，则必须满足全局最优解包含局部最优解。,但并不是所有,具有,最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法,动态规划（例如,“,0-1,背包问题,”,与,“,部分背包问题,”,）,57,【,问题,1】,部分背包问题,给定一个最大载重量为,M,的卡车和,N,种食品，有食盐，白糖，大米等。已知第,i,种食品的最多拥有,Wi,公斤，其商品价值为,Vi,元,/,公斤，编程确定一个装货方案使得装入卡车中的所有物品总价值最大。,【,分析,】,因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。,方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。,58,【,问题,2】0/1,背包问题,给定一个最大载重量为,M,的卡车和,N,种动物。已知第,i,种动物的重量为,Wi,，其最大价值为,Vi,，设定,M,，,Wi,，,Vi,均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。,【,分析,】,按贪心法：每次选价格最大的装载。很明显有反例：设,N=3,卡车最大载重量是,100,三种动物,A,、,B,、,C,的重量分别是,40,50,70,其对应的总价值分别是,90,、,100,、,150,。,59,贪心策略与其他算法的区别,1.,贪心与递推：,与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。,2.,贪心与动态规划：,与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。,60,几个简单的贪心例子,61,贪心策略,62,例题,1,：删数问题,键盘输入一个高精度的正整数,n,（,n=240,位）,去掉其中任意,s,个数字后剩下的数字按照原来的次序将组成一个新的正整数。编程对给定的,n,和,s,寻求一种方案,使得剩下组成的新数最小。,【,样例输入,】,178543,4,【,样例输出,】13,63,分析,由于正整数,n,的有效位数最大可达,240,位，所以可以采用字符串类型来存储,n,。那么，应如何来确定该删除哪,s,位呢？是不是只要删掉最大的,s,个数字就可以了呢？,为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程,s,次，剩下的数字串便是问题的解了。,64,例题,2,：排队问题,在一个食堂，有,n,个人排队买饭，每个人买饭需要的时间为,Ti,，请你找出一种排列次序，是每个人买饭的时间总和最小。,65,【,思路点拨,】,由题意可知，本题可以采用的贪心策略为：将,n,个人排队买饭的时间从小到大排序，再依次累加每人的买饭时间，即可得到最小的总和。由样例可知，排好序后的数据为,(1,3,5,7,9,11),，每个人的买饭时间如下：,T1=1,T2=T1+t2=1+3=4,T3=T2+t3=4+5=9,T4=T3+t4=9+7=16,T5=T4+t5=16+9=25,T6=T5+t6=25+11=36,总时间,T=T1+T2+T3+T4+T5+T6=91,66,用反证法证明如下：,假设一个不排好序的,n,个人也能得到最优答案。,比如把,(1,3,5,7,9,11),中的,3,5,对调一下，得到的序列为,(1,5,3,7,9,11),。,对调后，,3,5,前后的,1,7,9,11,四个人的买饭时间不会有变化，关键的变化是,3,5,两个人。这时，,5,这个人的买饭时间为,1+5,，,3,这个人的买饭时间变为,1+5+3,，此时两个人的总买饭时间中，,5,被累加了,2,次，而原方案中是,3,被累加了,2,次，其他一样。由此，两者相比较，可知有序的序列能得到最优的方案。,对于其他位置的改变可以采用同样的方法证明。用反证法证明时，关键是证明反例不成立，由此推出原方案是最优的。,67,问题推广：排队打水问题,有,n,个人排队到,r,个水龙头去打水，他们装满水桶的时间,t1,、,t2,.tn,为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？,68,例题,3,：打包,某工厂生产出的产品都要被打包放入正四棱柱的盒子内，所有盒子的高度为,h,，但地面尺寸不同，可以为,1x1,、,2x2,、,3x3,、,4x4,、,5x5,、,6x6,。如下图所示。,这些盒子将被放入高度为,h,，地面尺寸为,6x6,的箱子中。为了降低运送成本，工厂希望尽量减少箱子的数量。如果有一个好算法，能使箱子的数量降到最低，这将给工厂节省不少的资金。请你编写一个程序。,69,分析,70,分析,71,例题,4:,射击比赛（,CEOI1997,）,我们假设射击的目标是一个由,R*C(2RC,1000),个小方格组成的矩形网格。网格中每一列恰有,2,个白色的小方格和,R-2,个黑色的小方格。定义网格的行从顶至底编号为,1R,，列从左至右编号为,1C,。,射击者可射击,C,次。在连续的,C,次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。问题是，如果存在正确的射击方法，则要求找到它。,72,例如考虑如下目标：由上图可以看出，在每列中依次射中的行坐标为,23,1,4,。现在要求你编程计算出是否有正确的射击方法。,根据题设条件，射击的选择有,2,C,种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。,73,【,方法,1】,网络流算法,我们将表示列的点编号为,1,到,C,，表示行的点编号为,C+1,到,C+R,，如果一个白色方格处在第,i,行第,j,列，那么从点,j,向点,C+i,连一条弧，弧的容量为,1,。再增设一个源点,S,，从点,S,往点,1,到,C,间各连一条弧，弧的容量为,1,，又设一个汇点,T,，从点,C+1,到点,C+R,向汇点,T,连一条弧，弧的容量为,1,，那么从源点,S,到汇点,T,求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路线则描述了具体的射击方案。,显然，如果用网络流求出的最大流量比,R,小，则问题无解，否则我们可以根据网络流的结果求出该二分图的具体匹配方案。,74,红色,的连线流量为,1,蓝色,的连线流量为,0,选择的射击格即为：,(1,3),(2,1),(3,2),(4,4),S,2,1,4,3,2,1,4,3,T,列,:,行,:,源,:,汇,:,75,网络流算法经过优化，时间复杂度可以达到,O(C*(n+4C+4R),上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。,76,【,方法二,】,贪心方法,统计所有行包含的白格数,从还没有射击格的行中选出一个白格数最少的,检查所选的行,（,1,）若所选行的白格数为,0,，则输出无解；,（,2,）否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减,1,返回到第,2,步，直到所有的行都有射击格。,若还有列没有选射击格，则在该列任选一白格作为射击格即可,77,上面的贪心方法非常高效：,时间复杂度为,O,(,R,C,),，如果在程序中使用堆优化，时间复杂度将降为,O,(,R,log,2,C,),。空间复杂度是线性的，而且非常容易实现。,现在关键的问题就是,如何证明它的正确性？,78,证明：,用,hi,表示第,i,行的白格数。如果最开始的时候：,minhi=0,：第,i,行已经没有办法找到可作为射击格的白格，那么问题只能无解。,minhi=1,：那么第,i,行的这一个白格必须要作为射击格，否则将因第,i,行没有射击格而造成问题无解。,minhi2,：那么在这一行任选一个白格,顶多只会造成剩余行中有一行,h,值为,1,再处理那一行，最多也只会再造成剩余行中有一行,h,值为,1,，如此往复,将保持,h,值为,1,的行数不超过,1,行，最后最坏的情况也是造成最后一行的,h,值为,1,继续下去所有行就都已选取了射击格了。,因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。由此可以证明，此贪心方法是正确的。确定贪心标准。,79,贪心的经典应用,（一）、三个区间上的问题,1,、选择不相交区间问题,2,、区间选点问题,3,、区间覆盖问题,（二）、两个调度问题,1,、流水作业调度问题,2,、带限期和罚款的单位时间任务调度,（三）,Huffman,编码,（四）,最优合并问题,80,1,、选择不相交区间问题,给定,n,个开区间,(ai,bi),，选择尽量多个区间，使得这些区间两两没有公共点。,【,算法实现,】,首先按照,b1=b2=,=bn,的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。,贪心策略：取第一个区间；,【,正确性,】,：,如果不选,b1,，假设第一个选择的是,bi,，则如果,bi,和,b1,不交叉则多选一个,b1,更划算；如果交叉则把,bi,换成,b1,不影响后续选择。,81,例题,5,：活动安排,设有,n,个活动的集合,E=1,2,.,n,，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动,i,都有一个要求使用该资源的起始时间,si,和一个结束时间,fi,，且,si=sj,或,fj=si,时，活动,i,与活动,j,相容。选择出由互相兼容的活动组成的最大集合。,82,2,、区间选点问题,给定,n,个闭区间,ai,bi,，在数轴上选尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。,【,算法,】,：,首先按照,b1=b2=,=bn,排序。每次标记当前区间的右端点,X,，并右移当前区间指针，直到当前区间不包含,X,，再重复上述操作。,贪心策略：取最后一个。,83,例题,6,：种树（,NOIP,模拟试题）,一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为,1.n,。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码,b,e,t,。这三个数表示该居民想在,b,和,e,之间最少种,t,棵树。当然，,b=e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求,t=s,的,bi,的最大值即可。,87,例题,7,：区间（,SDOI2005,）,现给定,n,个闭区间,ai,bi,，,1=i=n,。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间,a,b,和,c,d,是按照升序排列的，那么我们有,ab=c=d,。任务：读入这些区间，计算满足给定条件的不相交闭区间，并把这些区间按照升序输出。,88,练习试题：喷水装置,有一块草坪，长为,L,，宽为,w,；,在它的中心线上装有,n,个点状的喷水装置，效果是让以它为中心半径为,ri,的圆被润湿，选择尽量少的喷水装置把整个草坪全部润湿。,89,1,、流水作业调度问题,样例,5 /作业个数,4 5 8 7 3 /,每个作业,M1,机器上加工时间,6 2 1 4 9 /,每个作业,M2,机器上加工时间,90,分析,91,2,、带限期和罚款的单位时间任务调度,7,2 4 1 4 6 4 3,60 50 30 20 10 70 40,92,贪心方法的推广,贪心与其它算法结合,搜索的最优化剪枝（,生日蛋糕）,优化动态规划（,Peter,的快餐店）,贪心方法与解题策略,最优方法不一定是最好方法,想不到最优解法就用较优解法,93,贪心与其它算法结合,例题,11,：,Peter,的快餐店,（贪心与动态规划）,Peter,最近在,R,市新开了一家快餐店。该快餐店准备推出一种套餐，每套由,A,个汉堡、,B,个薯条和,C,个饮料组成。为了提高产量，,Peter,引进了,N,条生产线。所有生产线都可以生产汉堡、薯条和饮料，由于每条生产线一天能工作的时间是有限的、不同的，而汉堡、薯条和饮料的单位生产时间又不同，,Peter,需要知道，怎样安排才能是一天中生产的套餐量最大。假设一天中汉堡、薯条和饮料的产量均不超过,100,个，且生产线总数小于等于,10,。,94,分析,本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。,状态表示：用,pijk,表示前,i,条生产线生产,j,个汉堡，,k,个薯条的情况下最多可生产饮料的个数。,用,rijk,表示第,i,条生产线生产,j,个汉堡，,k,个薯条的情况下最多可生产饮料的个数。,状态转移方程,:pijk=Maxpi-1j1k1+rij-j1k-k1,(0=j1=j,0=k1=k,且,(j-j1),*,p1+(k-k1)*p2=,第,i,条生产线的生产时间,),但这样的算法是非常粗糙的，稍加分析可以发现，此算法的时间复杂度为,O(N*100,4,),当,N=10,的时候，时间复杂度将达到,10*100,4,=10,9,，这是根本无法承受的。,95,用贪心方法作预处理,：,首先计算出一天生产套数的上限值：,min100 div A,100 div B,100 div C,接着，用贪心方法计算出这,N,条生产线可以生产的套数，并与上限比较，大于或等于则输出上限值并退出，否则再调用动态规划。因为贪心方法的代价很低，这里甚至可以使用多次贪心标准不同的贪心方法，取其最大值。,在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，将贪心思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提前结束程序。,96,算法步骤：,97,贪心小结,:,贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。,并且，贪心与其他算法的结合，可以对其他算法起到优化作用。,98,