第三次课 贪心算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 贪心法,第,3,章 内容提纲,3.1,贪心算法的基本思想,3.2,删数问题,3.3,装箱问题,顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的,局部最优,选择。,当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,活动安排问题,设有,n,个活动的集合,E=1,2,n,，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动,i,都有一个要求使用该资源的起始时间,si,和一个结束时间,fi,且,si,fi,。如果选择了活动,i,，则它在半开时间区间,si,fi,),内占用资源。若区间,si,fi,),与区间,sj,fj,),不相交，则称活动,i,与活动,j,是相容的。也就是说，当,si,fj,或,sj,fi,时，活动,i,与活动,j,相容。,活动安排问题,template,void,GreedySelector,(int,n,Type s,Type f,bool,A),A1=true;,int,j=1;,for(,int,i=2;i=,fj,),Ai,=true;j=i;,else,Ai,=false;,下面给出解活动安排问题的贪心算法,GreedySelector,:,各活动的起始时间和结束时间存储于数组,s,和,f,中且按结束时间的非减序排列,活动安排问题,由于输入的活动以其完成时间的,非减序,排列，所以算法,greedySelector,每次总是选择,具有最早完成时间,的相容活动加入集合,A,中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是,使剩余的可安排时间段极大化,，以便安排尽可能多的相容活动。,算法,greedySelector,的效率极高。当输入的活动已按结束时间的非减序排列，算法只需,O(n,),的时间安排,n,个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用,O(nlogn,),的时间重排。,活动安排问题,例：,设待安排的,11,个活动的开始时间和结束时间按结束时间的非减序排列如下：,i,1,2,3,4,5,6,7,8,9,10,11,Si,1,3,0,5,3,5,6,8,8,2,12,fi,4,5,6,7,8,9,10,11,12,13,14,活动安排问题,算法,greedySelector,的计算过程,如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合,A,的活动，而空白长条表示的活动是当前正在检查相容性的活动。,活动安排问题,若被检查的活动,i,的开始时间,Si,小于最近选择的活动,j,的结束时间,fi,，则不选择活动,i,，否则选择活动,i,加入集合,A,中。,贪心算法并不总能求得问题的,整体最优解,。但对于活动安排问题，贪心算法,greedySelector,却总能求得的整体最优解，即它最终所确定的相容活动集合,A,的规模最大。这个结论可以用数学归纳法证明。,贪心算法的基本要素,本节着重讨论可以用贪心算法求解的问题的一般特征。对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢,?,这个问题很难给予肯定的回答。,但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有,2,个重要的性质：,贪心选择性质,和,最优子结构性质,。,贪心算法的基本要素,1,、贪心选择性质,所谓,贪心选择性质,是指所求问题的,整体最优解,可以通过一系列,局部最优,的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。,动态规划算法通常以,自底向上,的方式解各子问题，而贪心算法则通常以,自顶向下,的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。,对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,贪心算法的基本要素,当一个问题的最优解包含其子问题的最优解时，称此问题具有,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,2,、最优子结构性质,贪心算法的基本要素,贪心算法和动态规划算法都要求问题具有最优子结构性质，这是,2,类算法的一个共同点。但是，对于具有,最优子结构,的问题应该选用贪心算法还是动态规划算法求解,?,是否能用动态规划算法求解的问题也能用贪心算法求解,?,下面研究,2,个经典的,组合优化问题,，并以此说明贪心算法与动态规划算法的主要差别。,3,、贪心算法与动态规划算法的差异,贪心算法的基本要素,0-1,背包问题：,给定,n,种物品和一个背包。物品,i,的重量是,Wi,，其价值为,Vi,，背包的容量为,C,。应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,在选择装入背包的物品时，对每种物品,i,只有,2,种选择，即装入背包或不装入背包。不能将物品,i,装入背包多次，也不能只装入部分的物品,i,。,贪心算法的基本要素,背包问题：,与,0-1,背包问题类似，所不同的是在选择物品,i,装入背包时，,可以选择物品,i,的一部分,，而不一定要全部装入背包，,1in,。,这,2,类问题都具有,最优子结构,性质，极为相似，但背包问题可以用贪心算法求解，而,0-1,背包问题却不能用贪心算法求解。,贪心算法的基本要素,首先计算每种物品单位重量的价值,Vi/,Wi,，然后，依贪心选择策略，将尽可能多的,单位重量价值最高,的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过,C,，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。,具体算法可描述如下页：,用贪心算法解背包问题的基本步骤：,贪心算法的基本要素,void,Knapsack,(int,n,float,M,float,v,float,w,float,x),Sort(n,v,w,);,int,i;,for(i=1;i=,n;i,+),xi,=0;,float c=M;,for(i=1;ic)break;,xi,=1;,c-=,wi,;,if(i=n),xi,=,c/wi,;,算法,knapsack,的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为,O,（,nlogn,）。,为了证明算法的正确性，还必须证明背包问题具有贪心选择性质,。,贪心算法的基本要素,对于,0-1,背包问题,，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑,0-1,背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用,动态规划算法,求解的另一重要特征。,实际上也是如此，动态规划算法的确可以有效地解,0-1,背包问题。,3.2,删数问题,给定一个高精度的正整数,N,（不超过,240,位），去掉任意,S,个数字后剩下的数字按原左右次序组成一个新的正整数。编程对于给定的,N,和,S,，寻找一种方案使得剩下的数字组成的新数最小,示例：,N=178543,，,S=4,则结果为：,13,算法分析,N,的存储只能采用数组，可选择字符数组；,可采用贪心算法，即：共删掉,S,个数，每一步删掉一个数，并且总选择一个使剩下的数最小的数符删去。,为了保证删,1,个数符后的数最小，可以按照从高位到低位的方向收缩递减区间，如果不存在递减区间则删尾数符；否则删掉递减区间的首字符，这样形成一个新的数串。然后回到串首，重复上面的规则，删下一个数符，。，直至删除,S,个数符为止。,1,7,8,5,4,3,1,7,5,4,3,1,5,4,3,1,4,3,1,3,1,7,8,5,3,4,1,7,5,3,4,1,5,3,4,1,3,4,1,3,程序,#include,#include,using namespace std;,int,s;,class node,public:,char c;,node*next;,;,class,quee,public:,node*first;,;,quee,*init(),char str250;,quee,*n;node*,tmp,;node*tail;,n=new,quee,;n-first=NULL;,cin,str,;,cin,s;int,i=0;,while(stri,!=0),tmp,=new node;,tmp,-c=,stri,;,tmp,-next=NULL;,if(n,-first=NULL),n-first=,tmp,;tail=,tmp,;,else,tail-next=,tmp,;tail=,tmp,;,i+;,return n;,;,void,del(quee,*start,node*p),node*x;,x=start-first;,if(x-next),while(x,-next!=p)x=x-next;,x-next=p-next;,delete p;,;,void,print(quee,*start),node*,tmp,;,if(start,-first=NULL)return;,tmp,=start-first;,while(tmp,),printf,(%,c,tmp,-c);,tmp,=,tmp,-next;,printf(n,);,;,node*,find(quee,*start),node*,tmp,;,tmp,=start-first;,while(tmp,-next!=NULL&,tmp,-cnext-c),tmp,=,tmp,-next;,return,tmp,;,;,int,main(int,argc,char*,argv,),quee,*n;,node*p;,n=init();,while(s,!=0),p=,find(n,);,del(n,p,);,s-;,print(n,);,return 0;,3.3 POJ 1017,Packets,Packets,题意,已知：有,6*6,的大箱子和,1*1,，,2*2,，,3*3,，,4*4,，,5*5,，,6*6,的木块,(,平面,),问：给定各种木块的数目，求最少需要多少个大箱子来装？,例如：,输入：,0 0 4 0 0 1 -,输出,2,输入：,7 5 1 0 0 0 -,输出,1,Packets,解题思想：,贪心准则：先放大的，后放小的,6*6,的木块每个占用一个箱子；,5*5,的木块每个占用一个新箱子，余下,11,个,1*1,的空格；,4*4,的木块每个占用一个新箱子，余下,5,个,2*2,的空格。,4.3*3,的木块每,4,个占用新一个箱子，不足,4,个也占一个新箱子，分情况余下不同数目的空格；,5.2*2,的木块先填空格，空格不足开新箱子，每,9,个,2*2,的木块占一个新箱子；,6.1*1,的木块先填空格，空格不足开新箱子，每,36,个占一个新箱子。,Packets,假设,6*6,，,5*5,，,4*4,，,3*3,，,2*2,，,1*1,的箱子个数,b6 b5 b4 b3 b2 b1,Packets,4*4,，,5*5,，,6*6,的块单独开新的箱子。,每一个,5*5,的块还能放下,11,个,1*1,的箱子。,每一个,4*4,的块还能放下,5,个,2*2,的箱子，或者放下,20,个,1*1,的箱子。,4*4,块,5*5,块,6*6,块,3*3,的块,1-4,块占一个新箱子，一个箱子可放下,4,个,3*3,的块。,如果一个箱子放下了,1,个,3*3,的块，则还可放下,5,个,2*2,的块和,7,个,1*1,的块。或者可以放下,27,个,1*1,的块。,如果一个箱子放下了,2,个,3*3,的块，则还可放下,3,个,2*2,的块和,6,个,1*1,的块。或者可以放下,18,个,1*1,的块。,如果一个箱子放下了,3,个,3*3,的块，则还可放下,1,个,2*2,的块和,5,个,1*1,的块。或者可以放下,9,个,1*1,的块。,Packets,nTotal,-,箱子数,1,）先放好所有,6*6,5*5,4*4,和,3*3,的木块,nTotal,=b6+b5+b4+(b3+3)/4,4*4,5*5,6*6,单独开新的箱子,3*3,每,1-4,个占一个新箱子,2,）再把,2*2,的塞到放有,3*3,木块的箱子里,int Contain24=0,5,3,1;,Contain2i,表示当箱子里有,i,个,3*3,的木块时，还能放下多少个,2*2,的木块,3,）考虑放有,3*3,的木块的箱子在塞满,2*2,的木后还能放多少个,1*1,的木块：,int Contain14=0,7,6,5;,Contain1i,表示当箱子里有,i,个,3*3,的木块，并且还填满了,2*2,的木块后，还能放下多少个,1*1,的木块。,Packets,如果箱子里放,1,个,3*3,木块，那么还能放,5,个,2*2,木块,以及,7,个,1*1,木块,Packets,如果箱子里放,2,个,3*3,木块，那么还能放,3,个,2*2,木块,以及,6,个,1*1,木块,Packets,如果箱子里放,3,个,3*3,木块，那么还能放,1,个,2*2,木块,以及,5,个,1*1,木块,Packets,4),计算放好,6*6,5*5,4*4,3*3,后留下多少空格能放,2*2,c2=b4*5+Contain2b3%4;,留下多少空格能放,1*1,c1=b5*11+,Contain1b3%4,(,能放,2*2,的地方暂不考虑放,1*1,，因为如果,c2b2,则多余的,b2-c2,个位置可以放,4*(b2-c2),个,1*1,的箱子,),Packets,5),放,2*2,，如果不够放，就开新箱子，放完,2*2,，计算还剩多少空格能放,1*1,。,if(b2 c1),nTotal,+=(b1-c1)/36;,if(b1-c1)%36),nTotal,+;,cout,nTotal,endl,;,Packets,#include,int,Contain14=0,7,6,5;,int,Contain24=0,5,3,1;,int,nTotal,;,void main(),int,b1,b2,b3,b4,b5,b6;,for(;),cin,b1b2b3b4b5b6;,if(b1=0&b2=0&b3=0&b4=0&b5=0&b6=0),break;,nTotal,=b6+b5+b4+b3/4;,if(b3%4),nTotal,+;,int,c1;/,当前能放,1*1,木块的空格数目,c1=b5*11;/,每个放,5*5,的箱子，还能放,11,个,1*1,的木块,c1+=Contain1b3%4;/,加上,3*3,箱子里能放的数目,int,c2;/,当前能放,2*2,木块的空格数目（先不考虑将,1*1,的木块放在,/2*2,的空格里）,c2=b4*5;/,每个放,5*4,的箱子，还能放,5,个,2*2,的木块,c2+=Contain2b3%4;/,加上,3*3,箱子里能放的数目,if(b2 c1),nTotal,+=(b1-c1)/36;,if(b1-c1)%36),nTotal,+;,cout,nTotal,endl,;,案例,3,水位,为使房屋买主可以评估洪水保险的开销，一家真实的房地产公司提供了一种客户端程序，此程序现实了可能被购买得房屋所在地区以,100,平方米为单位的海拔高度。雨水、雪水和管道破裂流出的水将会汇聚到海拔最低，因为水会从高处流向低处。为简化问题，我们假设水沿着排水沟从高出流向低处，并且水不会被土地所吸收。,从天气信息的档案中，我们得知了一个区域的典型储水量。作为预期的购房者，我们希望知道低处积水后的水位，以及完全被淹没在水中的面积占此地区的百分比,(,也就是，,10,平方米的海拔高度严格低于水平面,),。你被要求写一个程序来给出结果。,输入数据,输入包括区域描述所构成的一个序列。每个由一对整数,m,和,n,开始，每个都小于,30,，给定的区域都是,100,平方米。紧随其后的是,m,行，每行,n,个整数，给出地区海平面，以主行序给出。高度的单位是米，分别用正数或者负数表明高于或低于海平面。每个区域最后一个值是一个整数，用以指出有多少立方米的水聚集到此区域。,m,和,n,为两个,0,代表输入结束。,输出描述,对每个区域，显示区域编号,(1,2,),，水平面,(,以米为单位表示高于或低于海平面,),以及此区域被水淹没的面积，每个占一行。水位和被水淹没面积的百分率显示时保留,2,位小数每个区域输出后跟一个空行。,样例,3 3,25 37 45,51 12 34,94 83 27,10000,0 0,Region 1,Water level is 46.67 meters.,66.67 percent of the region is under water.,解题思路,由于题目中特别声明水无论如何都会流到当前水面最低的地方，使得问题一下子简化了。很容易想到以下贪心算法：,（,1,）把每个格子的高度排序；,（,2,）以低格子到高格子的顺序填水，把水均匀的铺在当前的水面上，并不断更新当前水面面积，和剩余水量；,（,3,）若剩余水量为,0,，输出当前水面高度和水面覆盖率。,注意,1,水面每达到一个格子的高度，水面的面积也要随之扩大；,2,高度有负值，水面的初始高度是最低格子的高度而不是,0,；,3,考虑好若干个格子高度相等的情况；,4,每个格子的面积是,100,；,5,没有水时，覆盖率为,0,；,6,水若刚好达到一个格子的高度，此格子不算被水覆盖；,7,水面达到最高格子后，要把剩下的水均匀的铺在整个区域上；,8,注意浮点数的计算误差，因为这个原因大家在,POJ,上都没有通过此题,:-,#include,#include,int,h1000000;,/,保存每个格子的高度值，因不知,m,和,n,的范围，故设的比较大,int,cmp(const,void*a,const void*b),return*(,int,*)a)-*(,int,*)b);,main(),int,t,m,n,nn,;,double x,hw;,int,i;,t=0;,while(1),/,输入,scanf(%d%d,if(n,=0,t+;,nn,=m*n;,for(i,=0;i 0),for(i,=1;i,nn,;i+),/,在高度相等的情况下，扩大水面面积,while(i,nn,&,hi,=,hi,-1),i+;,if(i,=,nn,|x 0)/,若剩下水，就把它铺在当前的范围上,while(i,1,且,B/A=BA,，则,C=B/A,若,A,1,，则,C=B,打印,1/C,转步骤（,2,）。,#include,#include,int,num;,int,a,b,;,int,c;,int,zc(int,a,int,b),int,xx;,xx=b/a;,if(xx,*a=b)return 1;,return 0;,;,void,calab,(),while(1),c=(b/a)+1;,a=a*,c-b,;,b=b*c;,printf(%d,c,);,if(a,1&,zc(a,b,),printf(%dn,b/a,);,break;,else,if(a,=1),printf(%dn,b,);,break;,;,main(),int,i;,scanf(%dn,&num,);,for(i,=1;i=,num;i,+),scanf(%d,%,dn,&a,&b,);,calab,();,最佳浏览路线问题,-50,17,-42,-47,-19,-3,-36,-34,-43,-30,-43,34,-23,-8,-45,南,北,西,东,课堂练习,校门外的树,某校大门外长度为,L,的马路上有一排树，每两棵相邻的树之间的间隔都是,1,米。我们可以把马路看成一个数轴，马路的一端在数轴,0,的位置，另一端在,L,的位置；数轴上的每个整数点，即,0,，,1,，,2,，,，,L,，,都种有一棵树。,由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。,课堂练习,校门外的树,【,输入文件,】,输入的第一行有两个整数,L,（,1=L=10000,）,和,M,（,1=M=100,），,L,代表马路的长度，,M,代表区域的数目，,L,和,M,之间用一个空格隔开。接下来的,M,行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。,【,输出文件,】,输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。,课堂练习,校门外的树,【,样例输入,】,500 3,150 300,100 200,470 471,【,样例输出,】,298,#include,#include,int,a10010;,int,main(),int,l,n,i,j,s,t,ans,;,while(,scanf(%d%d,&l,&n,)!=EOF),memset(a,0,sizeof(a);,for(i=0;i,n;i,+),scanf(%d%d,&s,&t,);,for(j=,s;j,=,t;j,+),aj,=1;,for(,ans,=0,i=0;i=,l;i,+)if(!,ai,),ans,+;,printf(%dn,ans,);,return 0;,方法二：区间合并,按区间的开始值对所有区间排序；,扫描合并,程序,方法三：排序扫描,