2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 贪心法二.doc

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 贪心法二课题：贪心法目标：知识目标：贪心的原理递与贪心的实现能力目标：贪心的原理重点：贪心算法的应用难点：贪心的理解板书示意：1） 贪心的引入（例24）2） 贪心的应用（例25、例26、例27、例28）授课过程：若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。下面我们看一些简单例题。例24：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:读入N, M,矩阵数据；Total := 0;For I := 1 to N do begin对N行进行选择 选择第I行最大的数,记为K； Total := Total + K；End；输出最大总和Total；从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。例25：部分背包问题给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。因此我们非常容易设计出如下算法：问题初始化； 读入数据按Vi从大到小将商品排序；I := 1;repeat if M = 0 then Break; 如果卡车满载则跳出循环 M := M - Wi; if M >= 0 then 将第I种商品全部装入卡车 else 将(M + Wi)重量的物品I装入卡车; I := I + 1; 选择下一种商品until (M <= 0) OR (I >= N)在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。Program Exam25;Const Finp=Input.Txt; Fout=Output.Txt;Var N,M :Longint; S :Real; P,W :Array1.100 Of Integer;Procedure Init; 输出Var I :Integer;Begin Assign(Input,Finp); Reset(Input); Readln(M,N); For I:=1 To N Do Readln(WI,PI); Close(Input);End;Procedure Sort(L,R:Integer); 按收益值从大到小排序Var I,J,Y :Integer; X :Real;Begin I:=L; J:=R; X:=P(L+R) Div 2/W(L+R) Div 2; Repeat While (I<R)And(PI/WI>=X) Do Inc(I); While (PJ/WJ<=X)And(J>L) Do Dec(J); If I<=J Then Begin Y:=PI; PI:=PJ; PJ:=Y; Y:=WI; WI:=WJ; WJ:=Y; Inc(I); Dec(J); End; Until I>J; If I<R Then Sort(I,R); If L<J Then Sort(L,J);End;Procedure Work;Var I :Integer;Begin Sort(1,N); For I:=1 To N Do If M>=WI Then 如果全部可取，则全取 Begin S:=S+PI; M:=M-WI; End Else 否则取一部分 Begin S:=S+M*(PI/WI); Break; End;End;Procedure Out; 输出Begin Assign(Output,Fout); Rewrite(Output); Writeln(S:0:0); Close(Output);End;Begin 主程序 Init; Work; Out;End.因此，利用贪心策略解题，需要解决两个问题：首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点： 可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。 原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。下面来看看0-1背包问题。给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。即确定一组X1，X2，Xn， Xi0,1f(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。没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。问题出现在什么地方呢？我们看看图2-18图23 卡车装载货物情况分析从图23中明显可以看出，情况A，卡车的空载率比情况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。例26排队打水问题有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？分析：由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：(1) 将输入的时间按从小到大排序；(2) 将排序后的时间按顺序依次放入每个水龙头的队列中； (3) 统计，输出答案。参考程序：Program Exam26;Const Finp=Input.Txt; Fout=Output.Txt;Var A :Array1.100 Of Integer; S :Array1.100 Of Longint; N,M :Integer; Min :Longint;Procedure Init; 读入数据Var I :Integer;Begin Assign(Input,Finp); Reset(Input); Readln(N,M); For I:=1 To N Do Read(AI); Close(Input);End;Procedure Sort(L,R:Integer); 将时间从小到大排序Var I,J,X,Y :Integer;Begin I:=L; J:=R; X:=A(L+R) Div 2; Repeat While (AI<=X)And(I<R) Do Inc(I); While (AJ>=X)And(J>L) Do Dec(J); If I<=J Then Begin Y:=AI; AI:=AJ; AJ:=Y; Inc(I); Dec(J); End; Until I>J; If L<J Then Sort(L,J); If R>I Then Sort(I,R);End;Procedure Work;Var I,J,K :Integer;Begin Fillchar(S,Sizeof(S),0); J:=0; Min:=0; For I:=1 To N Do 用贪心法求解 Begin Inc(J); If J=M+1 Then J:=1; SJ:=SJ+AI; Min:=Min+SJ; End; Assign(Output,Fout); Rewrite(Output); 输出解答 Writeln(Min); Close(Output);End;Begin 主程序 Init; Sort(1,N); Work;End.例27：旅行家的预算（NOI99分区联赛第3题）一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。样例：InputD1=275.6C=11.9D2=27.4 P=2.8 N=2油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2Output26.95（该数据表示最小费用）分析：需要考虑如下问题：1） 出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？2） 汽车行程到第几站开始加油，加多少油？可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。对于第一种情况，则油箱需要（d（j）-d（i）/m加仑汽油。对于第二种情况，则需将油箱加满。贪心算法证明如下：设定如下变量：Valuei：第i个加油站的油价；Overi：在第i站时的剩油；Wayi：起点到油站i的距离；XI：X记录问题的最优解，XI记录油站I的实际加油量。首先，X10，Over1=0。假设第I站加的XI一直开到第K站。则有，XI.xk-1都为0，而XK0。 若ValueI>Valuek，则按贪心方案，第I站应加油为T=（Wayk-WayI）/M-OverI。若T<XI，则汽车无法从起点到达第k个加油站；与假设矛盾。若T>XI, 则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用ValueI*W，如果W加仑汽油在油站K加，则须费用ValueK*W，显然ValueK*W<ValueI*W。 若ValueI<Valuek，则按贪心规则，须加油为 T=C-OverI（即加满油）。若T<XI，则表示在第I站的加油量会超过汽车的实际载油量，显然是不可能的。若T>XI，则表示在第I站的不加满油，而将一部分油留待第K站加，而ValueI<Valuek，所以这样费用更高。综合上述分析，可以得出如下算法：I := 1 汽车出发设定为第1个加油站L := C*D2； 油箱装满油能行驶的距离repeat 在L距离以内，向后找第一个油价比I站便宜的加油站J； if J存在 then if I站剩余油能到达J then 计算到达J站的剩油 else 在I站购买油，使汽车恰好能到达J站 else 在I站加满油； I := J； 汽车到达J站until 汽车到达终点；程序如下： program NOI99L_3; const Inp = input.txt; Outp = output.txt; MaxN = 10001;最大油站数 Zero = 1e-16;误差值 type Rectype = record油站的数据结构 Value: Real;油价 Way: Real;距起点的距离 Over: Real;汽车到达该站时的剩油 end; RecPtr = Rectype;油站指针 var Oil: array 1 . MaxN of RecPtr;记录所有油站 D1,起点到终点之间的距离 C,汽车油箱的容量 D2,每升汽油能行驶的距离 N: Integer;油站数 Cost: Real; 最小油费 MaxWay,满油时汽车最大的行驶距离 function init: Boolean; 初始化，并判无解 var I: Integer; begin Read (D1, C, D2); New(Oil1);处理初始值和起始油站 Oil1.Way := 0; Read(Oil1.Value,n); MaxWay := D2 * C; for I := 2 to n do begin 读入后N-1个油站信息 New(OilI);Readln(OilI.Way, OilI.Value);OilI.over:=0; end; Inc(n); 将终点也看成一个加油站 New(Oiln); Oiln.Way := D1;Oiln.Value := 0;Oiln.over:=0; for I := 2 to n+1 do 判是否无解 if (OilI.Way OilI 1.Way > MaxWay) then begin init:= False; Exit;end; init := True; end;procedure Buy(I: Integer; Miles: Real);在I加油站购买Miles/D2加仑汽油 begin Cost:= Cost + Miles / D2 * OilI.Value; 将买汽油所需的费用加到Cost变量中 end; procedure Solve; var I, J: Integer; S: Real; begin I := 1;汽车在起点 repeat S := 0.0;在MaxWay范围以内，找第一个油价比I站便宜的加油站J while (S <= MaxWay+zero) and (J <= N 1)and (OilI.Value <= OilJ.Value) dobegin Inc(J); S := S + OilJ.Way OilJ 1.Way; end;if S <= MaxWay+zero then 如果找到J站或可以直达终点如果剩油足够到达J站，则无需购油，并计算到达J站时汽车的剩油if (OilI.Over + Zero >=OilJ.Way OilI.Way) then OilJ.Over:=OilI.OverOilJ.Way+OilI.Way else begin 在I站购买恰好能到达J站的油量 Buy(I,OilJ.Way OilI.Way OilI.Over); OilJ.Over := 0.0; end else begin附近无比I站便宜的加油站J Buy(I, MaxWay OilI.Over);在I站加满油J := I + 1;行驶到下一站 OilJ.Over:= MaxWay (OilJ.Way OilI.Way); end; I := J;汽车直达J站 until I = N;汽车到达终点 end; begin主程序 Cost := 0; Assign(Input, Inp); Reset(Input); Assign(Output, Outp); Rewrite(Output); if init then begin 如果有解 Solve;求解 Writeln(Cost:0 :2);输出最少费用 end else Writeln(No Solution);输出无解 Close(Input); Close(Output); end.例28：两机器加工问题有n个部件需在A，B机器上加工，每个工件都必须经过先A后B两道工序。已知：部件i在A、B机器上的加工时间分别为ai，bi。问：如何安排n个工件的加工顺序，才能使得总加工时间最短？输入示例：N = 5工件I12345ai358710bi62149输出示例：34 （最少时间）1 5 4 2 3 （最优加工顺序）分析：本题求一个加工顺序使得加工总时间最短，要使时间最短，则就是让机器的空闲时间最短。一旦A机器开始加工，则A机器将会不停的进行作业，关键是B机器在加工过程中，有可能要等待A机器。很明显第一个部件在A机器上加工时，B机器必须等待，最后一个部件在B机器上加工，A机器也在等待B机器的完工。可以大胆猜想，要使总的空闲的最少，就要把在A机器上加工时间最短的部件最先加工，这样使得B机器能以最快的速度开始加工；把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：设Mi=minai, bi将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的已经作业后面，若Mi=bi，则将它排在从尾开始的作业前面。例如：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=b3m3排在后面；加入m3之后的加工顺序为（ ， ， ， ，3）；处理m2：m2=b2m2排在后面；加入m2之后的加工顺序为（ ， ， ，2，3）；处理m1：m3=a1m1排在前面；加入m1之后的加工顺序为（1， ， ，2，3）；处理m4：m4=b4m4排在后面；加入m4之后的加工顺序为（1， ，4，2，3）；处理m5：m5=b5m5排在后面；加入m5之后的加工顺序为（1，5，4，2，3）；则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。问题是这种贪心策略是否正确呢？还需证明。证明过程如下：设S=J1，J2，Jn，为待加工部件的作业排序，若A机器开始加工S中的部件时，B机器还在加工其它部件，t时刻后再可利用，在这样的条件下，加工S中任务所需的最短时间T（S，t）= minai+T(S-Ji,bi+maxt-ai,0) 其中，JiS。图24 机器加工作业示意图从图24可以看出，（a）为作业I等待机器B的情况，（b）为机器B等待作业I在机器A上完成的情形。假设最佳的方案中，先加工作业Ji，然后加工作业Jj，则有：T(S,t)=ai+T(S-Ji,bi+Maxt-ai,0) =ai+aj+T(S-Ji,Jj,bj+maxbi+maxt-ai,0-aj,0) =ai+aj+T(S-Ji,Jj,Tij)Tij=bj+maxbi+maxt-ai,0-aj,0 =bj+bi-aj+maxmaxt-ai,0,aj-bi =bi+bj-aj+maxt-ai,aj-bi,0 =bi+bj-ai-aj+maxt,ai,ai+aj-bi若maxt,ai,ai+aj-bi=t若maxt,ai,ai+aj-bi=ai若maxt,ai,ai+aj-bi=ai+aj-bi若将作业Ji和作业Jj的加工顺序，则有：T(S,t)=ai+aj+T(S-(Ji,Jj),Tji)，其中Tji=bi+bj-ai-aj+maxt,aj,ai+aj-bj按假设，因为T<=T,所以有:maxt,ai+aj-bi,ai<=maxt,ai+aj-bj,aj 于是有：ai+aj+max-bi,-aj<=ai+aj+max-bj,-ai即Minbj,ai<=minbi,aj 式便是Johnson公式。也就是说式成立的条件下，任务Ji安排在任务Jj之前加工可以得到最优解。也就是说在A机器上加工时间短的任务应优先，而在B机器上加工时间短的任务应排在后面。因此，论证了开始设计的贪心算法是正确的。算法流程如下：for I := 1 to N do 求M数组 if AI < BI thenMI := AI elseMI := BI；将M从小到大排序；S := 1; T := N;首位指针初始化for I := 1 to N do if 对于第I小的工序J，若AJ < BJ then begin OrderS := J; 将工序J插在加工序列的前面 S := S + 1; end else begin OrderT := J; 将工序J插在加工序列的后面 T := T - 1; end;程序如下：program Machine; const Inp = input.txt; Outp = output.txt; MaxN = 100;最多部件数 var N, Min: Integer; A, B, M, O, O用来记录从小到大排序后部件的编号 Order: array 1 . MaxN of Integer;Order用来记录加工顺序 procedure Init;读入数据 var I: Integer; begin Assign(Input, Inp); Reset(Input); Readln(N); for I := 1 to N do Read(AI); Readln; for I := 1 to N do Read(BI); Close(Input); end; procedure Main; var I, J, Z, S, T, T1, T2: Integer; begin FillChar(M, Sizeof(M), 0);求M数组的值 for I := 1 to N do if AI < BI then MI := AI else MI := BI; for I := 1 to N do OI := I; for I := 1 to N - 1 do从小到大排序 for J := I + 1 to N do if MOI > MOJ then begin Z := OI; OI :=OJ; OJ := Z; end; FillChar(Order, Sizeof(Order), 0); S := 1; T := N; for I := 1 to N do if MOI = AOI then begin 若AOI<BOI，则插在加工序列的前面 OrderS := OI; S := S + 1; end else begin 若BOIAOI，则插在加工序列的后面 OrderT := OI; T := T - 1; end; 计算最少加工时间 T1 := 0; T2 := 0; for I := 1 to N do begin T1 := T1 + AOrderI; if T2 < T1 then T2 := T1; T2 := T2 + BOrderI; end; Min := T2; end; procedure Out;打印输出 var I: Integer; begin Assign(Output, Outp); Rewrite(Output); Writeln(Min);输出最少时间 for I := 1 to N do输出最佳加工序列 Write(OrderI, ); Writeln; Close(Output); end; Begin Init;输入 Main;主过程 Out;输出 End.