2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 貪心法二.doc

2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 貪心法二課題：貪心法目標：知識目標：貪心的原理遞與貪心的實現(xiàn)能力目標：貪心的原理重點：貪心算法的應用難點：貪心的理解板書示意：1） 貪心的引入（例24）2） 貪心的應用（例25、例26、例27、例28）授課過程：若在求解一個問題時，能根據(jù)每次所得到的局部最優(yōu)解，推導出全局最優(yōu)或最優(yōu)目標。那么，我們可以根據(jù)這個策略，每次得到局部最優(yōu)解答，逐步而推導出問題，這種策略稱為貪心法。下面我們看一些簡單例題。例24：在N行M列的正整數(shù)矩陣中，要求從每行中選出1個數(shù)，使得選出的總共N個數(shù)的和最大。分析：要使總和最大，則每個數(shù)要盡可能大，自然應該選每行中最大的那個數(shù)。因此，我們設計出如下算法:讀入N, M,矩陣數(shù)據(jù)；Total := 0;For I := 1 to N do begin對N行進行選擇 選擇第I行最大的數(shù),記為K； Total := Total + K；End；輸出最大總和Total；從上例中我們可以看出，和遞推法相仿，貪心法也是從問題的某一個初始解出發(fā)，向給定的目標遞推。但不同的是，推進的每一步不是依據(jù)某一固定的遞推式，而是做一個局部的最優(yōu)選擇，即貪心選擇（在例中，這種貪心選擇表現(xiàn)為選擇一行中的最大整數(shù)），這樣，不斷的將問題歸納為若干相似的子問題，最終產生出一個全局最優(yōu)解。特別注意的是是，局部貪心的選擇是否可以得出全局最優(yōu)是能否采用貪心法的關鍵所在。對于能否使用貪心策略，應從理論上予以證明。下面我們看看另一個問題。例25：部分背包問題給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價值為Vi元/公斤，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大。分析：因為每一個物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。因此我們非常容易設計出如下算法：問題初始化； 讀入數(shù)據(jù)按Vi從大到小將商品排序；I := 1;repeat if M = 0 then Break; 如果卡車滿載則跳出循環(huán) M := M - Wi; if M >= 0 then 將第I種商品全部裝入卡車 else 將(M + Wi)重量的物品I裝入卡車; I := I + 1; 選擇下一種商品until (M <= 0) OR (I >= N)在解決上述問題的過程中，首先根據(jù)題設條件，找到了貪心選擇標準(Vi)，并依據(jù)這個標準直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法。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.因此，利用貪心策略解題，需要解決兩個問題：首先，確定問題是否能用貪心策略求解；一般來說，適用于貪心策略求解的問題具有以下特點： 可通過局部的貪心選擇來達到問題的全局最優(yōu)解。運用貪心策略解題，一般來說需要一步步的進行多次的貪心選擇。在經過一次貪心選擇之后，原問題將變成一個相似的，但規(guī)模更小的問題，而后的每一步都是當前看似最佳的選擇，且每一個選擇都僅做一次。 原問題的最優(yōu)解包含子問題的最優(yōu)解，即問題具有最優(yōu)子結構的性質。在背包問題中，第一次選擇單位質量最大的貨物，它是第一個子問題的最優(yōu)解，第二次選擇剩下的貨物中單位重量價值最大的貨物，同樣是第二個子問題的最優(yōu)解，依次類推。其次，如何選擇一個貪心標準？正確的貪心標準可以得到問題的最優(yōu)解，在確定采用貪心策略解決問題時，不能隨意的判斷貪心標準是否正確，尤其不要被表面上看似正確的貪心標準所迷惑。在得出貪心標準之后應給予嚴格的數(shù)學證明。下面來看看0-1背包問題。給定一個最大載重量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價值為Vi，設定M，Wi，Vi均為整數(shù)，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價值最大。分析：對于N種動物，要么被裝，要么不裝，也就是說在滿足卡車載重的條件下，如何選擇動物，使得動物價值最大的問題。即確定一組X1，X2，Xn， Xi0,1f(x)=max(Xi*Vi) 其中，(Xi*Wi)W從直觀上來看，我們可以按照上例一樣選擇那些價值大，而重量輕的動物。也就是可以按價值質量比（Vi/Wi）的大小來進行選擇?？梢钥闯?，每做一次選擇，都是從剩下的動物中選擇那些Vi/Wi最大的，這種局部最優(yōu)的選擇是否能滿足全局最優(yōu)呢？我們來看看一個簡單的例子：設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?？梢缘玫絻r值80+100=180，卡車裝載的重量為40+50=90。沒有超過卡車的實際載重，因此也是一種可行解，顯然，這種解比上一種解要優(yōu)化。問題出現(xiàn)在什么地方呢？我們看看圖2-18圖23 卡車裝載貨物情況分析從圖23中明顯可以看出，情況A，卡車的空載率比情況B高。也就是說，上面的分析，只考慮了貨物的價值質量比，而沒有考慮到卡車的運營效率，因此，局部的最優(yōu)化，不能導致全局的最優(yōu)化。因此，貪心不能簡單進行，而需要全面的考慮，最后得到證明。例26排隊打水問題有N個人排隊到R個水龍頭去打水，他們裝滿水桶的時間為T1，T2，Tn為整數(shù)且各不相等，應如何安排他們的打水順序才能使他們花費的時間最少？分析：由于排隊時，越靠前面的計算的次數(shù)越多，顯然越小的排在越前面得出的結果越?。梢杂脭?shù)學方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：(1) 將輸入的時間按從小到大排序；(2) 將排序后的時間按順序依次放入每個水龍頭的隊列中； (3) 統(tǒng)計，輸出答案。參考程序：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; 讀入數(shù)據(jù)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分區(qū)聯(lián)賽第3題）一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發(fā)時油箱時空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點每升汽油價格P和沿途加油站數(shù)N（N可以為零），油站i離出發(fā)點的距離Di、每升汽油價格Pi（i=1，2，N）。計算結果四舍五入至小數(shù)點后兩位。如果無法到達目的地，則輸出“No Solution”。樣例：InputD1=275.6C=11.9D2=27.4 P=2.8 N=2油站號I離出發(fā)點的距離Di每升汽油價格Pi1102.02.92220.02.2Output26.95（該數(shù)據(jù)表示最小費用）分析：需要考慮如下問題：1） 出發(fā)前汽車的油箱是空的，故汽車必須在起點（1號站）處加油。加多少油？2） 汽車行程到第幾站開始加油，加多少油？可以看出，原問題需要解決的是在哪些油站加油和加多少油的問題。對于某個油站，汽車加油后到達下一加油站，可以歸結為原問題的子問題。因此，原問題關鍵在于如何確定下一個加油站。通過分析，我們可以選擇這樣的貪心標準：對于加油站I，下一個加油站J可能第一個是比油站I油價便宜的油站，若不能到達這樣的油站，則至少需要到達下一個油站后，繼續(xù)進行考慮。對于第一種情況，則油箱需要（d（j）-d（i）/m加侖汽油。對于第二種情況，則需將油箱加滿。貪心算法證明如下：設定如下變量：Valuei：第i個加油站的油價；Overi：在第i站時的剩油；Wayi：起點到油站i的距離；XI：X記錄問題的最優(yōu)解，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，則按貪心規(guī)則，須加油為 T=C-OverI（即加滿油）。若T<XI，則表示在第I站的加油量會超過汽車的實際載油量，顯然是不可能的。若T>XI，則表示在第I站的不加滿油，而將一部分油留待第K站加，而ValueI<Valuek，所以這樣費用更高。綜合上述分析，可以得出如下算法：I := 1 汽車出發(fā)設定為第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;最大油站數(shù) Zero = 1e-16;誤差值 type Rectype = record油站的數(shù)據(jù)結構 Value: Real;油價 Way: Real;距起點的距離 Over: Real;汽車到達該站時的剩油 end; RecPtr = Rectype;油站指針 var Oil: array 1 . MaxN of RecPtr;記錄所有油站 D1,起點到終點之間的距離 C,汽車油箱的容量 D2,每升汽油能行駛的距離 N: Integer;油站數(shù) 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 （最優(yōu)加工順序）分析：本題求一個加工順序使得加工總時間最短，要使時間最短，則就是讓機器的空閑時間最短。一旦A機器開始加工，則A機器將會不停的進行作業(yè)，關鍵是B機器在加工過程中，有可能要等待A機器。很明顯第一個部件在A機器上加工時，B機器必須等待，最后一個部件在B機器上加工，A機器也在等待B機器的完工?？梢源竽懖孪?，要使總的空閑的最少，就要把在A機器上加工時間最短的部件最先加工，這樣使得B機器能以最快的速度開始加工；把在B機器上加工時間最短的部件放在最后加工。這樣使得A機器能盡快的等待B機器完工。于是我們可以設計出這樣的貪心法：設Mi=minai, bi將M按照從小到大的順序排序。然后從第1個開始處理，若Mi=ai，則將它排在從頭開始的已經作業(yè)后面，若Mi=bi，則將它排在從尾開始的作業(yè)前面。例如：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）；則最優(yōu)加工順序就是（1，5，4，2，3），最短時間為34。顯然這是最優(yōu)解。問題是這種貪心策略是否正確呢？還需證明。證明過程如下：設S=J1，J2，Jn，為待加工部件的作業(yè)排序，若A機器開始加工S中的部件時，B機器還在加工其它部件，t時刻后再可利用，在這樣的條件下，加工S中任務所需的最短時間T（S，t）= minai+T(S-Ji,bi+maxt-ai,0) 其中，JiS。圖24 機器加工作業(yè)示意圖從圖24可以看出，（a）為作業(yè)I等待機器B的情況，（b）為機器B等待作業(yè)I在機器A上完成的情形。假設最佳的方案中，先加工作業(yè)Ji，然后加工作業(yè)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若將作業(yè)Ji和作業(yè)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之前加工可以得到最優(yōu)解。也就是說在A機器上加工時間短的任務應優(yōu)先，而在B機器上加工時間短的任務應排在后面。因此，論證了開始設計的貪心算法是正確的。算法流程如下：for I := 1 to N do 求M數(shù)組 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;最多部件數(shù) var N, Min: Integer; A, B, M, O, O用來記錄從小到大排序后部件的編號 Order: array 1 . MaxN of Integer;Order用來記錄加工順序 procedure Init;讀入數(shù)據(jù) 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數(shù)組的值 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.