ACM贪心算法

贪心算法贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。肥猫的粮食（HD1009）•FatMousepreparedMpoundsofcatfood,readytotradewiththecatsguardingthewarehousecontaininghisfavoritefood,JavaBean.ThewarehousehasNrooms.Thei-throomcontainsJ[i]poundsofJavaBeansandrequiresF[i]poundsofcatfood.FatMousedoesnothavetotradeforalltheJavaBeansintheroom,instead,hemaygetJ[i]*a%poundsofJavaBeansifhepaysF[i]*a%poundsofcatfood.Hereaisarealnumber.Nowheisassigningthishomeworktoyou:tellhimthemaximumamountofJavaBeanshecanobtain.•Theinputconsistsofmultipletestcases.Eachtestcasebeginswithalinecontainingtwonon-negativeintegersMandN.ThenNlinesfollow,eachcontainstwonon-negativeintegersJ[i]andF[i]respectively.Thelasttestcaseisfollowedbytwo-1's.Allintegersarenotgreaterthan1000.•Foreachtestcase,printinasinglelinearealnumberaccurateupto3decimalplaces,whichisthemaximumamountofJavaBeansthatFatMousecanobtain.肥猫的粮食（HD1009）输入：53724352203251824151510-1-1输出：13.33331.500#includestdio.hintmain(){intm,n,a[1001],b[1001],i,j,t;doubles,max,c[1001];while(scanf(%d%d,&m,&n)&&(m!=-1||n!=-1)){for(i=0;in;i++){scanf(%d%d,&a[i],&b[i]);c[i]=a[i]*1.0/b[i];}s=0;for(i=0;in;i++){max=0;t=0;for(j=0;jn;j++)if(maxc[j]){max=c[j];t=j;}if(m=b[t]){s=s+a[t];m=m-b[t];}else{s=s+m*1.0/b[t]*a[t];break;}c[t]=0;}printf(%.3lf\n,s);}return0;}过河问题•描述–进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。–输入•第一行输入s,表示测试数据的组数；每组数据的第一行包括两个整数w，n，80=w=200,1=n=300，w为一条独木舟的最大承载量,n为人数；接下来的一组数据为每个人的重量（不能大于船的承载量）；–输出•每组人数所需要的最少独木舟的条数。样例输入38565848580848390390456010055050904060样例输出53301.02.#includeiostream03.#includealgorithm04.usingnamespacestd;05.intmain()06.{07.intv;08.cinv;09.while(v--)10.{11.intw,n,*p,t;12.cinwn;13.p=newint[n];14.for(inti=0;in;i++)15.{cint;p[i]=t;}16.sort(p,p+n);17.inti=0,k=n-1,count=0;18.while(i=k)19.{20.if(2*p[i]=w)21.{while((p[i]+p[k]w)&&(ik)){count++;--k;}22.if(i==k)count++;23.else{count++;--k;}24.}25.else26.{if(i==k)count++;27.else{count+=2;--k;}28.}29.++i;30.}31.coutcountendl;}32.return0;33.}今年暑假不AC（2037）•Input•输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e(1=i=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。•Output•对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。SampleInput1213340738151915201015818612510414290SampleOutput5活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。活动安排问题例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314活动安排问题算法greedySelector的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。活动安排问题若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。2037代码•#includestdio.h•voidmain()•{•inta[105],b[105],n,i,j,t,w;•intcount=0;•while(scanf(%d,&n)!=EOF)•{if(n==0)•break;•for(i=0;in;i++)•scanf(%d%d,&a[i],&b[i]);•for(i=0;in-1;i++)•for(j=0;jn-i-1;j++)•if(b[j]b[j+1])•{•t=b[j];b[j]=b[j+1];b[j+1]=t;•t=a[j];a[j]=a[j+1];a[j+1]=t;•}•w=0;count=0;•for(i=1;in;i++)•{•if(a[i]=b[w])•{count++;w=i;•}••}•printf(%d\n,count+1);•}•}贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。贪心算法的基本要素1.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。贪心算法的基本要素2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。活动安排问题证明•贪心选择性质证明：•设E={1，2，……，n}为所给活动集合。由于E中活动按结束时间的非减序排列，故活动1具有最早的完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解包含活动1。AE是所给问题的最优解，且A中活动也是按结束时间非减序排列，A中第一个活动是k。若k=1，则A就是一个以贪心选择开始的最优解。若k1,设B={A-{k}}{1}，由于f1=fk,且A中活动是相容的，故B中的活动也是相容的。又由于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。也就是说，B是一个以贪心选择活动为1开始的最优安排。因此，我们证明了总存在一个以贪心选择开始的最优活动安排。活动安排问题证明•最优子结构性质证明：•若A是原问题的一个最优解，则A’=A-{1}是活动问题E’={iE:sif1}的一个最优解。•事实上，如果我们能找到一个E’的一个解B’，它包含比A’更多的活动，则将活动1加入到B’中将产生E的一个解B，它包含比A更多的活动。这与A的最优性矛盾。因此，每一步所作的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。搬桌子1050•SampleInput•3•4•1020•3040•5060•7080•2•13•2200•3•10100•2080•3050•SampleOutput•10•20•30附:参考源码(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;}删数字问题•键盘上输入一个高精度的正整数n，去掉任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。•12435863•k=3•删除k位后结果：12353删数字问题•在位数固定的前提下，让高位数字尽量小。•n=231183•k=3•3比2大则删除3，21183•2比1大删除2，1183•8比3大删除8，113删数字问题•当k=1时，从左到右每相邻两数比较，若出现增，即左边小于右边，则删除右边的大数字。若不出现增，则删除最右边的大数字。•当k1时，重复以上操作。网络赛1003Transferwater•Description•Greeprylivesinavillage.Lastyearfloodrainedthevil