《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ù)學證明。
下面來看看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）的大小來進行選擇?？梢钥闯觯孔鲆淮芜x擇，都是從剩下的動物中選擇那些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。可以得到價值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ù)學方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：
(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)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法二.doc
鏈接地址：http://www.820124.com/p-2613326.html