第五讲贪心算法课件

第五讲贪心算法1一二请在这里输入您的主要叙述内容整体概述三请在这里输入您的主要叙述内容请在这里输入您的主要叙述内容2一、引入：若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。例如：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。3分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:读入N,M,矩阵数据；Total:=0;ForI:=1toNdobegin {对N行进行选择}选择第I行最大的数,记为K；Total:=Total+K；End；输出最大总和Total；4从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。特别注意的是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。5二、应用举例例1：部分背包问题给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Pi，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。6分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。7问题初始化； {读入数据}按Pi/Wi从大到小将商品排序；I:=1;repeatifM=0thenBreak; {如果卡车满载则跳出循环}M:=M-Wi;ifM>=0then将第I种商品全部装入卡车else将(M+Wi)重量的物品I装入卡车;I:=I+1; {选择下一种商品}until(M<=0)OR(I>=N)

在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Pi/Wi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。8ProgramExam1;ConstFinp='Input.Txt';Fout='Output.Txt';VarN,M:Longint;S:Real;P,W:Array[1..100]OfInteger;ProcedureInit;{输出}VarI:Integer;BeginAssign(Input,Finp);Reset(Input);Readln(M,N);ForI:=1ToNDoReadln(W[I],P[I]);Close(Input);End;9ProcedureSort(L,R:Integer);{按收益值从大到小排序}VarI,J,Y:Integer;X:Real;BeginI:=L;J:=R;

X:=P[(L+R)Div2]/W[(L+R)Div2];RepeatWhile(I<R)And(P[I]/W[I]>=X)DoInc(I);While(P[J]/W[J]<=X)And(J>L)DoDec(J);IfI<=JThenBeginY:=P[I];P[I]:=P[J];P[J]:=Y;Y:=W[I];W[I]:=W[J];W[J]:=Y;Inc(I);Dec(J);End;UntilI>J;IfI<RThenSort(I,R);IfL<JThenSort(L,J);End;10ProcedureWork;VarI:Integer;BeginSort(1,N);S:=0;ForI:=1ToNDoIfM>=W[I]Then{如果全部可取，则全取}BeginS:=S+P[I];M:=M-W[I];EndElse{否则取一部分}BeginS:=S+M*(P[I]/W[I]);Break;End;End;11ProcedureOut;{输出}BeginAssign(Output,Fout);Rewrite(Output);Writeln(S:0:0);Close(Output);End;Begin{主程序}Init;Work;Out;End.12因此，利用贪心策略解题，需要解决两个问题：首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：(1）可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。(2)原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。13下面来看看0-1背包问题。给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。14分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。即确定一组X1，X2，…，Xn，Xi∈{0,1}f(x)=max(∑Xi*Vi)其中，∑(Xi*Wi)≦W从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（Vi/Wi）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些Vi/Wi最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子：设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。情况A：按照上述思路，三种动物的Vi/Wi分别为2,2,2.14。显然，我们首先选择动物C，得到价值150，然后任意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。情况B：不按上述约束条件，直接选择A和B。可以得到价值80+100=180，卡车装载的重量为40+50=90。没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。15问题出现在什么地方呢？我们看看图23，卡车装载货物情况分析

从图23中明显可以看出，情况A，卡车的空载率比情况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。图23卡车装载货物情况分析16例2、排队打水问题有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？17分析：由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：（1）将输入的时间按从小到大排序；（2）将排序后的时间按顺序依次放入每个水龙头的队列中；（3）统计，输出答案。18ProgramExam2;ConstFinp='Input.Txt';Fout='Output.Txt';VarA:Array[1..100]OfInteger;S:Array[1..100]OfLongint;N,M:Integer;Min:Longint;ProcedureInit;{读入数据}VarI:Integer;BeginAssign(Input,Finp);Reset(Input);Readln(N,M);ForI:=1ToNDoRead(A[I]);Close(Input);End;19ProcedureSort(L,R:Integer);{将时间从小到大排序}VarI,J,X,Y:Integer;BeginI:=L;J:=R;X:=A[(L+R)Div2];RepeatWhile(A[I]<=X)And(I<R)DoInc(I);While(A[J]>=X)And(J>L)DoDec(J);IfI<=JThenBeginY:=A[I];A[I]:=A[J];A[J]:=Y;Inc(I);Dec(J);End;UntilI>J;IfL<JThenSort(L,J);IfR>IThenSort(I,R);End;20ProcedureWork;VarI,J,K:Integer;BeginFillchar(S,Sizeof(S),0);J:=0;Min:=0;ForI:=1ToNDo{用贪心法求解}BeginInc(J);IfJ=M+1ThenJ:=1;S[J]:=S[J]+A[I];Min:=Min+S[J];End;Assign(Output,Fout);Rewrite(Output);{输出解答}Writeln(Min);Close(Output);End;21Begin{主程序}Init;Sort(1,N);Work;End.22例3：旅行家的预算（NOI99分区联赛第3题）一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，…，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“NoSolution”。样例：InputD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2Output26.95（该数据表示最小费用）23分析：需要考虑如下问题：(1)出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？(2)汽车行程到第几站开始加油，加多少油？可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。对于第一种情况，则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况，则需将油箱加满。24贪心算法证明如下：设定如下变量：Value[i]：第i个加油站的油价；Over[i]：在第i站时的剩油；Way[i]：起点到油站i的距离；X[I]：X记录问题的最优解，X[I]记录油站I的实际加油量。首先，X[1]≠0，Over[1]=0。假设第I站加的X[I]一直开到第K站。则有，X[I]..x[k-1]都为0，而X[K]≠0。若Value[I]>Value[k]，则按贪心方案，第I站应加油为:T=（Way[k]-Way[I]）/M-Over[I]。若T<X[I]，则汽车无法从起点到达第k个加油站；与假设矛盾。若T>X[I],则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用Value[I]*W，如果W加仑汽油在油站K加，则须费用Value[K]*W，显然Value[K]*W<Value[I]*W。若Value[I]<Value[k]，则按贪心规则，须加油为T=C-Over[I] （即加满油）。若T<X[I]，则表示在第I站的加油量会超过汽车的实际载油量，显然是不可能的。若T>X[I]，则表示在第I站的不加满油，而将一部分油留待第K站加，而Value[I]<Value[k]，所以这样费用更高。25综合上述分析，可以得出如下算法：I:=1{汽车出发设定为第1个加油站}L:=C*D2；{油箱装满油能行驶的距离}repeat在L距离以内，向后找第一个油价比I站便宜的加油站J；ifJ存在thenifI站剩余油能到达Jthen计算到达J站的剩油else在I站购买油，使汽车恰好能到达J站 else在I站加满油；I:=J； {汽车到达J站}until汽车到达终点；26programNOI99L_3;constInp=‘input.txt’;Outp=‘output.txt’;MaxN=10001; {最大油站数}Zero=1e-16; {误差值}typeRectype=record {油站的数据结构}Value:Real; {油价}Way:Real; {距起点的距离}Over:Real; {汽车到达该站时的剩油能行驶的里程}end;RecPtr=^Rectype; {油站指针}varOil:array[1..MaxN]ofRecPtr; {记录所有油站}D1, {起点到终点之间的距离} C, {汽车油箱的容量}D2, {每升汽油能行驶的距离}N:Integer; {油站数} Cost:Real; {最小油费}MaxWay, {满油时汽车最大的行驶距离}27functioninit:Boolean; {初始化，并判无解}varI:Integer;beginRead(D1,C,D2);New(Oil[1]); {处理初始值和起始油站}Oil[1]^.Way:=0;Read(Oil[1]^.Value,n); MaxWay:=D2*C;forI:=2tondobegin{读入后N-1个油站信息}New(Oil[I]); Readln(Oil[I]^.Way,Oil[I]^.Value);Oil[I]^.over:=0;end;Inc(n); {将终点也看成一个加油站}New(Oil[n]);Oil[n]^.Way:=D1;Oil[n]^.Value:=0;Oil[n]^.over:=0;forI:=2ton+1do {判是否无解}if(Oil[I]^.Way–Oil[I–1]^.Way>MaxWay)thenbegininit:=False;Exit;end;init:=True;end;28procedureBuy(I:Integer;Miles:Real);; {在I加油站购买Miles/D2加仑汽油}beginCost:=Cost+Miles/D2*Oil[I]^.Value;{将买汽油所需的费用加到Cost变量中}end;29procedureSolve;varI,J:Integer;S:Real;beginI:=1; {汽车在起点}repeatS:=0.0;{在MaxWay范围以内，找第一个油价比I站便宜的加油站J}while(S<=MaxWay+zero)and(J<=N–1)and(Oil[I]^.Value<=Oil[J]^.Value)dobeginInc(J);S:=S+Oil[J]^.Way–Oil[J–1]^.Way;end;ifS<=MaxWay+zerothen{如果找到J站或可以直达终点}{如果剩油足够到达J站，则无需购油，并计算到达J站时汽车的剩油}if(Oil[I]^.Over+Zero>=Oil[J]^.Way–Oil[I]^.Way)thenOil[J]^.Over:=Oil[I]^.Over–Oil[J]^.Way+Oil[I]^.Wayelsebegin{在I站购买恰好能到达J站的油量}Buy(I,Oil[J]^.Way–Oil[I]^.Way–Oil[I]^.Over);Oil[J]^.Over:=0.0; endelsebegin {附近无比I站便宜的加油站J}Buy(I,MaxWay–Oil[I]^.Over); {在I站加满油}J:=I+1; {行驶到下一站}Oil[J]^.Over:=MaxWay–(Oil[J]^.Way–Oil[I]^.Way);end;I:=J; {汽车直达J站}untilI=N; {汽车到达终点}end;30begin {主程序} Cost:=0; Assign(Input,Inp);Reset(Input);Assign(Output,Outp);Rewrite(Output);ifinitthenbegin {如果有解}Solve; {求解}Writeln(Cost:0:2); {输出最少费用}endelseWriteln(‘NoSolution’); {输出无解}Close(Input);Close(Output);end.31例4：两机器加工问题

有n个部件需在A，B机器上加工，每个工件都必须经过先A后B两道工序。

已知：部件i在A、B机器上的加工时间分别为ai，bi。

问：如何安排n个工件的加工顺序，才能使得总加工时间最短？

输入示例：

N=5输出示例：34（最少时间）15423（最优加工顺序）工件I12345ai358710bi6214932分析：本题求一个加工顺序使得加工总时间最短，要使时间最短，则就是让机器的空闲时间最短。一旦A机器开始加工，则A机器将会不停的进行作业，关键是B机器在加工过程中，有可能要等待A机器。很明显第一个部件在A机器上加工时，B机器必须等待，最后一个部件在B机器上加工，A机器也在等待B机器的完工。可以大胆猜想，要使总的空闲的最少，就要把在A机器上加工时间最短的部件最先加工，这样使得B机器能以最快的速度开始加工；把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：设Mi=min{ai,bi}将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的已经作业后面，若Mi=bi，则将它排在从尾开始的作业前面。33例如：N=5（a1，a2，a3，a4，a5）=（3，5，8，7，10）（b1，b2，b3，b4，b5）=（6，2，1，4，9）则（m1，m2，m3，m4，m5）=（3，2，1，4，9）排序之后为（m3，m2，m1，m4，m5）处理m3：∵m3=b3∴m3排在后面；加入m3之后的加工顺序为（，，，，3）；处理m2：∵m2=b2∴m2排在后面；加入m2之后的加工顺序为（，，，2，3）；处理m1：∵m3=a1∴m1排在前面；加入m1之后的加工顺序为（1，，，2，3）；处理m4：∵m4=b4∴m4排在后面；加入m4之后的加工顺序为（1，，4，2，3）；处理m5：∵m5=b5∴m5排在后面；加入m5之后的加工顺序为（1，5，4，2，3）；则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。问题是这种贪心策略是否正确呢？还需证明。34证明过程如下：设S={J1，J2，……，Jn}，为待加工部件的作业排序，若A机器开始加工S中的部件时，B机器还在加工其它部件，t时刻后再可利用，在这样的条件下，加工S中任务所需的最短时间T（S，t）=min{ai+T(S-{Ji},bi+max{t-ai,0})}其中，Ji∈S。从图24可以看出，（a）为作业I等待机器B的情况，（b）为机器B等待作业I在机器A上完成的情形。35假设最佳的方案中，先加工作业Ji，然后加工作业Jj，则有：T(S,t)=ai+T(S-{Ji},bi+Max{t-ai,0})=ai+aj+T(S-{Ji,Jj},bj+max{bi+max{t-ai,0}-aj,0})

=ai+aj+T(S-{Ji,Jj},Tij)Tij=bj+max{bi+max{t-ai,0}-aj,0}=bj+bi-aj+max{max{t-ai,0},aj-bi}=bi+bj-aj+max{t-ai,aj-bi,0}=bi+bj-ai-aj+max{t,ai,ai+aj-bi}若max{t,ai,ai+aj-bi}=t若max{t,ai,ai+aj-bi}=ai若max{t,ai,ai+aj-bi}=ai+aj-bi36若将作业Ji和作业Jj的加工顺序，则有：T’(S,t)=ai+aj+T(S-(Ji,Jj),Tji)，其中Tji=bi+bj-ai-aj+max{t,aj,ai+aj-bj}按假设，因为T<=T’,所以有:max{t,ai+aj-bi,ai}<=max{t,ai+aj-bj,aj}…………①于是有：ai+aj+max{-bi,-aj}<=ai+aj+max{-bj,-ai}即Min{bj,ai}<=min{bi,aj}………………②

②式便是Johnson公式。也就是说②式成立的条件下，任务Ji安排在任务Jj之前加工可以得到最优解。也就是说在A机器上加工时间短的任务应优先，而在B机器上加工时间短的任务应排在后面。因此，论证了开始设计的贪心算法是正确的。37算法流程如下：forI:=1toNdo {求M数组}ifA[I]<B[I]then M[I]:=A[I] else M[I]:=B[I]；将M从小到大排序；S:=1;T:=N; {首位指针初始化}forI:=1toNdoif对于第I小的工序J，若A[J]<B[J]thenbeginOrder[S]:=J; {将工序J插在加工序列的前面}S:=S+1;endelsebeginOrder[T]:=J; {将工序J插在加工序列的后面}T:=T-1;end;38programMachine;constInp='input.txt';Outp='output.txt';MaxN=100; {最多部件数}varN,Min:Integer;A,B,M,O,{O用来记录从小到大排序后部件的编号}Order:array[1..MaxN]ofInteger; {Order用来记录加工顺序}procedureInit; {读入数据}varI:Integer;beginAssign(Input,Inp);Reset(Input);Readln(N);forI:=1toNdoRead(A[I]);Readln;forI:=1toNdoRead(B[I]);Close(Input);end;39

procedureMain;varI,J,Z,S,T,T1,T2:Integer;beginFillChar(M,Sizeof(M),0); {求M数组的值}forI:=1toNdoifA[I]<B[I]thenM[I]:=A[I]elseM[I]:=B[I];

forI:=1toNdoO[I]:=I;forI:=1toN-1do {从小到大排序}forJ:=I+1toNdoifM[O[I]]>M[O[J]]thenbeginZ:=O[I];O[I]:=O[J];O[J]:=Z;end;FillChar(Order,Sizeof(Order),0);S:=1;T:=N;forI:=1toNdoifM[O[I]]=A[O[I]]thenbegin{若A[O[I]]<B[O[I]]，则插在加工序列的前面}Order[S]:=O[I];S:=S+1;endelsebegin{若B[O[I]]≧A[O[I]]，则插在加工序列的后面}Order[T]:=O[I];T:=T-1;end;{计算最少加工时间}T1:=0;T2:=0;forI:=1toNdobeginT1:=T1+A[Order[I]];ifT2<T1thenT2:=T1;T2:=T2+B[Order[I]];end;Min:=T2;end;40procedureOut; {打印输出}varI:Integer;beginAssign(Output,Outp);Rewrite(Output);Writeln(Min); {输出最少时间}forI:=1toNdo {输出最佳加工序列}Write(Order[I],''); Writeln;Close(Output);end;BeginInit; {输入}Main; {主过程}Out; {输出}End.41贪心方法的基本思想

贪心是一种解题策略，也是一种解题思想使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解如何选择贪心标准，以得到问题的最优解

42适用于贪心策略求解的问题的特点

适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法——动态规划（例如“0-1背包问题”与“部分背包问题”）

43贪心方法的应用例题1：节点网络。现有一个N！个节点的网络，每个节点的编号都是编号（A1A2A3…AN）序列的一个置换。对于任意两个节点S和T，如果T的编号是由S编号的首位与除首位外的编号中任一位交换所得，则S和T之间有一条边，求从给定节点S走到节点（A1A2A3…AN）所需经过的最少边数。其中，n≤100。44贪心方法的应用例如n=3的情况：(A1A2A3)(A1A3A2)(A2A3A1)(A2A1A3)(A3A1A2)(A3A2A1)45贪心方法的应用【分析】从题意表面上看，本题是一个求最短路径的问题，但题设中的N≤100，也就是说图中最多有100！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。46贪心方法的应用采用贪心策略：每次让一个节点归位或为下一步工作做准备。其具体步骤为：若序列中第一个点为Ax(x≠1)，则将第一个点和第x个点交换。这便完成了让一个点归位的工作；若第一个是A1，则任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到1号位置的点归位。47贪心方法的应用(A3A4A1A2)(A1A4A3A2)第一个点A1已归位，但第二个点为A4≠A2，将第2个点A4与A1交换第一个点为A3≠A1，将第3个点A1与A3交换(A4A1A3A2)第一个点为A4≠A1，将第4个点A2与A4交换(A2A1A3A4)第一个点为A2≠A1，将第2个点A1与A2交换(A1A2A3A4)已经符合要求了一共经过4步完成。下面看一个n=4，初始序列为(A3A4A1A2)的推演过程：48贪心方法的应用例题2：d-规则问题。对任意给定的m(m∈N+)和n(n∈N+)，满足m<n，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)现定义一种d规则如下：若存在a∈P，且存在K∈N+,K>1，使得K

a∈P，则修改P为：P=P-{y|y=s

a,s∈N+}

，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。49贪心方法的应用【分析】初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=3，n=10时，集合P＝{3,…,10}，运用上述“贪心标准”可以得到这一问题的正确的最优解d=5＋4＋3＝12，即其d-规则过程如下：1.a=5P={3,4,6,7,8,9} d=52.a=4P={3,6,7,9} d=5+4=93.a=3p={7} d=5+4+3=1250贪心方法的应用但是，如果再仔细地分析一个例子，当m=3，n＝18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d＝38，其对应的d-规则序列为（9,8,7,6,3,5）。为什么会出现这样的反例呢？这是因为，问题中要使得d-规则总分d值越大，不光是要求每一个d分值越大越好，也要求取得的d分值越多越好。因此，本题不能采用纯粹的贪心策略求解。51贪心方法的应用【改进】将原算法基础上进行改进。下面给出新的算法：建立集合P={m..n}从ndiv2到m每数构造一个集合c[i]，包含该数在P中的所有倍数（不包括i本身）从ndiv2起找到第一个元素个数最少但又不为空的集合c[i]在d分值中加上i把i及c[i]集合从P集中删除，更新所有构造集合的元素检查所有构造集合，若还有非空集合，则继续3步骤，否则打印、结束52贪心方法的应用下面看m=3,n=18时的推演过程：初始P={3..18}找到i=9,c[i]={18},P={3..8,10..17}找到i=8,c[i]={16},P={3..7,10..15,17}找到i=7,c[i]={14},P={3..6,10..13,15,17}找到i=6,c[i]={12},P={3..5,10,11,13,15,17}找到i=3,c[i]={15},P={4,5,10,11,13,17}找到i=5,c[i]={10},P={4,11,13,17}到此所有构造集合全部为空，d=9+8+7+6+3+5=3853贪心方法的应用讨论：能否证明此贪心策略是正确的？能否找到其他更好的算法？54贪心方法的应用例题3：射击竞赛射击的目标是一个由R

C(2≤R≤C≤1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1~R，列从左至右编号为1~C。射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。55贪心方法的应用射击的选择有2C种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。56贪心方法的应用【方法一】网络流算法我们将表示列的点编号为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求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路线则描述了具体的射击方案。可以看出，如果