《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法二.doc》由會員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法二.doc（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法二
課題：貪心法
目標：
知識目標：貪心的原理遞與貪心的實現(xiàn)
能力目標：貪心的原理
重點：貪心算法的應(yīng)用
難點：貪心的理解
板書示意：
1） 貪心的引入（例24）
2） 貪心的應(yīng)用（例25、例26、例27、例28）
授課過程：
若在求解一個問題時，能根據(jù)每次所得到的局部最優(yōu)解，推導(dǎo)出全局最優(yōu)或最優(yōu)目標。那么，我們可以根據(jù)這個策略，每次得到局部最優(yōu)解答，逐步而推導(dǎo)出問題，這種策略稱為貪心法。
下面我們看一些簡單例題。
例24：在N行M列的正整數(shù)矩陣中，要求從每行中選出1個數(shù)，使得選出的總共N個數(shù)的和最大。
分析：要使總和最大，則每個數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個數(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ù)），這樣，不斷的將問題歸納為若干相似的子問題，最終產(chǎn)生出一個全局最優(yōu)解。
特別注意的是是，局部貪心的選擇是否可以得出全局最優(yōu)是能否采用貪心法的關(guān)鍵所在。對于能否使用貪心策略，應(yīng)從理論上予以證明。下面我們看看另一個問題。
例25：部分背包問題
給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價值為Vi元/公斤，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大。
分析：因為每一個物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。
因此我們非常容易設(shè)計出如下算法：
問題初始化； {讀入數(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ù)題設(shè)條件，找到了貪心選擇標準(Vi)，并依據(jù)這個標準直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法。
Program Exam25;
Const Finp=Input.Txt;
Fout=Output.Txt;
Var N,M :Longint;
S :Real;
P,W :Array[1..100] Of Integer;
Procedure Init; {輸出}
Var I :Integer;
Begin
Assign(Input,Finp); Reset(Input);
Readln(M,N);
For I:=1 To N Do Readln(W[I],P[I]);
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
=X) Do Inc(I);
While (P[J]/W[J]<=X)And(J>L) Do Dec(J);
If I<=J Then
Begin
Y:=P[I]; P[I]:=P[J]; P[J]:=Y;
Y:=W[I]; W[I]:=W[J]; W[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If I=W[I] Then {如果全部可取，則全取}
Begin
S:=S+P[I]; M:=M-W[I];
End
Else {否則取一部分}
Begin
S:=S+M*(P[I]/W[I]); 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)解。運用貪心策略解題，一般來說需要一步步的進行多次的貪心選擇。在經(jīng)過一次貪心選擇之后，原問題將變成一個相似的，但規(guī)模更小的問題，而后的每一步都是當前看似最佳的選擇，且每一個選擇都僅做一次。
② 原問題的最優(yōu)解包含子問題的最優(yōu)解，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。在背包問題中，第一次選擇單位質(zhì)量最大的貨物，它是第一個子問題的最優(yōu)解，第二次選擇剩下的貨物中單位重量價值最大的貨物，同樣是第二個子問題的最優(yōu)解，依次類推。
其次，如何選擇一個貪心標準？正確的貪心標準可以得到問題的最優(yōu)解，在確定采用貪心策略解決問題時，不能隨意的判斷貪心標準是否正確，尤其不要被表面上看似正確的貪心標準所迷惑。在得出貪心標準之后應(yīng)給予嚴格的數(shù)學(xué)證明。
下面來看看0-1背包問題。
給定一個最大載重量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價值最大。
分析：對于N種動物，要么被裝，要么不裝，也就是說在滿足卡車載重的條件下，如何選擇動物，使得動物價值最大的問題。
即確定一組X1，X2，…，Xn， Xi∈{0,1}
f(x)=max(∑Xi*Vi) 其中，∑(Xi*Wi)≦W
從直觀上來看，我們可以按照上例一樣選擇那些價值大，而重量輕的動物。也就是可以按價值質(zhì)量比（Vi/Wi）的大小來進行選擇?？梢钥闯?，每做一次選擇，都是從剩下的動物中選擇那些Vi/Wi最大的，這種局部最優(yōu)的選擇是否能滿足全局最優(yōu)呢？我們來看看一個簡單的例子：
設(shè)N=3，卡車最大載重量是100，三種動物A、B、C的重量分別是40，50，70，其對應(yīng)的總價值分別是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高。也就是說，上面的分析，只考慮了貨物的價值質(zhì)量比，而沒有考慮到卡車的運營效率，因此，局部的最優(yōu)化，不能導(dǎo)致全局的最優(yōu)化。
因此，貪心不能簡單進行，而需要全面的考慮，最后得到證明。
例26排隊打水問題
有N個人排隊到R個水龍頭去打水，他們裝滿水桶的時間為T1，T2，…，Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們花費的時間最少？
分析：由于排隊時，越靠前面的計算的次數(shù)越多，顯然越小的排在越前面得出的結(jié)果越小（可以用數(shù)學(xué)方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：
(1) 將輸入的時間按從小到大排序；
(2) 將排序后的時間按順序依次放入每個水龍頭的隊列中；
(3) 統(tǒng)計，輸出答案。
參考程序：
Program Exam26;
Const Finp=Input.Txt;
Fout=Output.Txt;
Var A :Array[1..100] Of Integer;
S :Array[1..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(A[I]);
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 (A[I]<=X)And(I=X)And(J>L) Do Dec(J);
If I<=J Then
Begin
Y:=A[I]; A[I]:=A[J]; A[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If LI 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;
S[J]:=S[J]+A[I];
Min:=Min+S[J];
End;
Assign(Output,Fout); Rewrite(Output); {輸出解答}
Writeln(Min);
Close(Output);
End;
Begin {主程序}
Init;
Sort(1,N);
Work;
End.
例27：旅行家的預(yù)算（NOI99分區(qū)聯(lián)賽第3題）
一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱時空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點每升汽油價格P和沿途加油站數(shù)N（N可以為零），油站i離出發(fā)點的距離Di、每升汽油價格Pi（i=1，2，……，N）。
計算結(jié)果四舍五入至小數(shù)點后兩位。
如果無法到達目的地，則輸出“No Solution”。
樣例：
Input
D1=275.6 C=11.9 D2=27.4 P=2.8 N=2
油站號I
離出發(fā)點的距離Di
每升汽油價格Pi
1
102.0
2.9
2
220.0
2.2
Output
26.95（該數(shù)據(jù)表示最小費用）
分析：需要考慮如下問題：
1） 出發(fā)前汽車的油箱是空的，故汽車必須在起點（1號站）處加油。加多少油？
2） 汽車行程到第幾站開始加油，加多少油？
可以看出，原問題需要解決的是在哪些油站加油和加多少油的問題。對于某個油站，汽車加油后到達下一加油站，可以歸結(jié)為原問題的子問題。因此，原問題關(guān)鍵在于如何確定下一個加油站。通過分析，我們可以選擇這樣的貪心標準：
對于加油站I，下一個加油站J可能第一個是比油站I油價便宜的油站，若不能到達這樣的油站，則至少需要到達下一個油站后，繼續(xù)進行考慮。
對于第一種情況，則油箱需要（d（j）-d（i））/m加侖汽油。對于第二種情況，則需將油箱加滿。
貪心算法證明如下：
設(shè)定如下變量：
Value[i]：第i個加油站的油價；
Over[i]：在第i站時的剩油；
Way[i]：起點到油站i的距離；
X[I]：X記錄問題的最優(yōu)解，X[I]記錄油站I的實際加油量。
首先，X[1]≠0，Over[1]=0。
假設(shè)第I站加的X[I]一直開到第K站。則有，X[I]..x[k-1]都為0，而X[K]≠0。
① 若Value[I]>Value[k]，則按貪心方案，第I站應(yīng)加油為
T=（Way[k]-Way[I]）/M-Over[I]。
若TX[I], 則預(yù)示著，汽車開到油站K，仍然有油剩余。假設(shè)剩余W加侖汽油，則須費用Value[I]*W，如果W加侖汽油在油站K加，則須費用Value[K]*W，顯然Value[K]*WX[I]，則表示在第I站的不加滿油，而將一部分油留待第K站加，而Value[I] MaxWay) then begin
init:= False;
Exit;
end;
init := True;
end;
procedure Buy(I: Integer; Miles: Real);;
{在I加油站購買Miles/D2加侖汽油}
begin
Cost:= Cost + Miles / D2 * Oil[I]^.Value;
{將買汽油所需的費用加到Cost變量中}
end;
procedure Solve;
var
I, J: Integer;
S: Real;
begin
I := 1; {汽車在起點}
repeat
S := 0.0;
{在MaxWay范圍以內(nèi)，找第一個油價比I站便宜的加油站J}
while (S <= MaxWay+zero) and (J <= N – 1)
and (Oil[I]^.Value <= Oil[J]^.Value) do
begin
Inc(J);
S := S + Oil[J]^.Way – Oil[J – 1]^.Way;
end;
if S <= MaxWay+zero then {如果找到J站或可以直達終點}
{如果剩油足夠到達J站，則無需購油，并計算到達J站時汽車的剩油}
if (Oil[I]^.Over + Zero >=Oil[J]^.Way – Oil[I]^.Way) then
Oil[J]^.Over:=Oil[I]^.Over–Oil[J]^.Way+Oil[I]^.Way
else begin
{在I站購買恰好能到達J站的油量}
Buy(I,Oil[J]^.Way – Oil[I]^.Way – Oil[I]^.Over);
Oil[J]^.Over := 0.0;
end
else begin {附近無比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站}
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機器上加工，每個工件都必須經(jīng)過先A后B兩道工序。
已知：部件i在A、B機器上的加工時間分別為ai，bi。
問：如何安排n個工件的加工順序，才能使得總加工時間最短？
輸入示例：
N = 5
工件I
1
2
3
4
5
ai
3
5
8
7
10
bi
6
2
1
4
9
輸出示例：
34 （最少時間）
1 5 4 2 3 （最優(yōu)加工順序）
分析：
本題求一個加工順序使得加工總時間最短，要使時間最短，則就是讓機器的空閑時間最短。一旦A機器開始加工，則A機器將會不停的進行作業(yè)，關(guān)鍵是B機器在加工過程中，有可能要等待A機器。很明顯第一個部件在A機器上加工時，B機器必須等待，最后一個部件在B機器上加工，A機器也在等待B機器的完工。
可以大膽猜想，要使總的空閑的最少，就要把在A機器上加工時間最短的部件最先加工，這樣使得B機器能以最快的速度開始加工；把在B機器上加工時間最短的部件放在最后加工。這樣使得A機器能盡快的等待B機器完工。于是我們可以設(shè)計出這樣的貪心法：
設(shè)Mi=min{ai, bi}
將M按照從小到大的順序排序。然后從第1個開始處理，若Mi=ai，則將它排在從頭開始的已經(jīng)作業(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=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）；
則最優(yōu)加工順序就是（1，5，4，2，3），最短時間為34。顯然這是最優(yōu)解。
問題是這種貪心策略是否正確呢？還需證明。
證明過程如下：
設(shè)S={J1，J2，……，Jn}，為待加工部件的作業(yè)排序，若A機器開始加工S中的部件時，B機器還在加工其它部件，t時刻后再可利用，在這樣的條件下，加工S中任務(wù)所需的最短時間T（S，t）= min{ai+T(S-{Ji},bi+max{t-ai,0})} 其中，Ji∈S。
圖24 機器加工作業(yè)示意圖
從圖24可以看出，（a）為作業(yè)I等待機器B的情況，（b）為機器B等待作業(yè)I在機器A上完成的情形。
假設(shè)最佳的方案中，先加工作業(yè)Ji，然后加工作業(yè)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-bi
若將作業(yè)Ji和作業(yè)Jj的加工順序，則有：
T’(S,t)=ai+aj+T(S-(Ji,Jj),Tji)，其中
Tji=bi+bj-ai-aj+max{t,aj,ai+aj-bj}
按假設(shè)，因為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公式。也就是說②式成立的條件下，任務(wù)Ji安排在任務(wù)Jj之前加工可以得到最優(yōu)解。也就是說在A機器上加工時間短的任務(wù)應(yīng)優(yōu)先，而在B機器上加工時間短的任務(wù)應(yīng)排在后面。因此，論證了開始設(shè)計的貪心算法是正確的。
算法流程如下：
for I := 1 to N do {求M數(shù)組}
if A[I] < B[I] then
M[I] := A[I]
else
M[I] := B[I]；
將M從小到大排序；
S := 1; T := N; {首位指針初始化}
for I := 1 to N do
if 對于第I小的工序J，若A[J] < B[J] then begin
Order[S] := J; {將工序J插在加工序列的前面}
S := S + 1;
end else begin
Order[T] := 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(A[I]);
Readln;
for I := 1 to N do
Read(B[I]);
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 A[I] < B[I] then M[I] := A[I] else M[I] := B[I];
for I := 1 to N do O[I] := I;
for I := 1 to N - 1 do {從小到大排序}
for J := I + 1 to N do
if M[O[I]] > M[O[J]] then begin
Z := O[I]; O[I] :=O[J]; O[J] := Z;
end;
FillChar(Order, Sizeof(Order), 0);
S := 1; T := N;
for I := 1 to N do
if M[O[I]] = A[O[I]] then begin
{若A[O[I]]
下載提示(請認真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認領(lǐng)！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
9.9
積分
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
-
2019-2020年高中信息技術(shù)
全國青少年奧林匹克聯(lián)賽教案
貪心法二
2019
2020
年高
信息技術(shù)
全國青少年
奧林匹克
聯(lián)賽
教案
貪心
- 溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法二.doc
鏈接地址：http://zhongcaozhi.com.cn/p-2613326.html