貪心算法詳解

1、貪心算法詳解貪心算法思想：顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。貪心算法的基本要素：1貪心選擇性質。所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃

2、算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行,以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。2. 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。貪心算法的基本思路：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到算法中的某一步不能再繼續(xù)前進時，算法停止。該算法存在問題：1. 不能保證求得的最后解是最佳的；2

3、. 不能用來求最大或最小解問題；3. 只能求滿足某些約束條件的可行解的范圍。實現該算法的過程：從問題的某一初始解出發(fā)；while能朝給定總目標前進一步do求出可行解的一個解元素；由所有解元素組合成問題的一個可行解；用背包問題來介紹貪心算法：背包問題：有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。物品ABCDEFG重量35306050401025價值10403050354030分析如下目標函數：工pi最大約束條件是裝入的物品總重量不超過背包容量：工wiv=M(M=150)。(1) 根據貪心的策略，每次挑選價值最大的

4、物品裝入背包，得到的結果是否最優(yōu)？(2) 每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？(3) 每次選取單位重量價值最大的物品，成為解本題的策略。值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經過證明成立后，它就是一種高效的算法。貪心算法還是很常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難?？上У氖牵枰C明后才能真正運用到題目的算法中。一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的。對于背包問題中的3種貪心策略，都是無法成立(無法被證明)的，解釋如下：貪心策略：選取價值最大者。反例：W=30物品：ABC重量：281212

5、價值：302020根據策略，首先選取物品A,接下來就無法再選取了，可是，選取B、C則更好。(2) 貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。(3) 貪心策略：選取單位重量價值最大的物品。反例：W=30物品：ABC重量：282010價值：282010根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A,則答案錯誤。但是果在條件中加一句當遇見單位價值相同的時候，優(yōu)先裝重量小的，這樣的問題就可以解決.所以需要說明的是，貪心算法可以與隨機化算法一起使用，具體的例子就不再多舉了。(因為這一類算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什

6、么，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確)。下面我們看一些簡單例題。例24：在N行M列的正整數矩陣中，要求從每行中選出1個數，使得選出的總共N個數的和最大。分析：要使總和最大，則每個數要盡可能大，自然應該選每行中最大的那個數。因此，我們設計出如下算法:讀入N,M,矩陣數據；Total:=0;ForI:=1toNdobegin對N行進行選擇選擇第I行最大的數記為K；Total:=Total+；KEnd；輸岀最大總和Total；從上例中我們可以看出，和遞推法相仿，貪心法也是從問題的某一個初始解出發(fā)，向給定的目標遞推。但不同的是，推進的每一步不是依據某一固定的遞推式，而是做一個

7、局部的最優(yōu)選擇，即貪心選擇(在例中，這種貪心選擇表現為選擇一行中的最大整數)，這樣，不斷的將問題歸納為若干相似的子問題，最終產生出一個全局最優(yōu)解。特別注意的是是，局部貪心的選擇是否可以得出全局最優(yōu)是能否采用貪心法的關鍵所在對于能否使用貪心策略，應從理論上予以證明。下面我們看看另一個問題。例25：部分背包問題給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有W公斤，其商品價值為V元/公斤，編程確定一個裝貨方案，使得裝入卡車中的ii所有物品總價值最大。分析：因為每一個物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法

8、解答，方法如下：先將單位塊收益按從大到小進行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。因此我們非常容易設計出如下算法：問題初始化；讀入數據按V從大到小將商品排序；iI:=1;repeatifM=0thenBreak;如果卡車滿載則跳出循環(huán)M:=M-W;iifM>=0then將第I種商品全部裝入卡車else將(M+W)重量的物品I裝入卡車iI:=I+1;選擇下一種商品until(M<=0)OR(I>=N)在解決上述問題的過程中，首先根據題設條件，找到了貪心選擇標準(V)，并依據這個i標準直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法。ProgramEx

9、am25;ConstFinp='Input.Txt'Fout='Output.Txt'VarN,MP,WProcedureInit;VarIBegin輸出:Longint;:Real;:Array1.100OfInteger;:Integer;Assign(Input,Finp);Reset(Input);Readln(M,N);ForI:=1ToNDoReadln(WI,PI);Close(Input);End;ProcedureSort(L,R:Integer);按收益值從大到小排序VarI,J,Y:Integer;X:Real;BeginI:=L;J:=R

10、;X:=P(L+R)Div2/W(L+R)Div2;RepeatWhile(I<R)And(PI/WI>=X)DoInc(I);While(PJ/WJ<=X)And(J>L)DoDec(J);IfI<=JThenBeginY:=PI;PI:=PJ;PJ:=Y;Y:=WI;WI:=WJ;WJ:=Y;Inc(I);Dec(J);End;UntilI>J;IfI<RThenSort(I,R);IfL<JThenSort(L,J);End;ProcedureWork;VarI:Integer;BeginSort(1,N);ForI:=1ToNDoIfM&

11、gt;=WIThen如果全部可取，則全取BeginS:=S+PI;M:=M-WI;EndElse否則取一部分BeginS:=S+M*(PI/WI);Break;End;End;ProcedureOut;輸出BeginAssign(Output,Fout);Rewrite(Output);Writeln(S:0:0);Close(Output);End;Begin主程序Init;Work;Out;End.因此，利用貪心策略解題，需要解決兩個問題：首先，確定問題是否能用貪心策略求解；一般來說，適用于貪心策略求解的問題具有以下特點： 可通過局部的貪心選擇來達到問題的全局最優(yōu)解。運用貪心策略解題，一般

12、來說需要一步步的進行多次的貪心選擇。在經過一次貪心選擇之后，原問題將變成一個相似的，但規(guī)模更小的問題，而后的每一步都是當前看似最佳的選擇，且每一個選擇都僅做一次。 原問題的最優(yōu)解包含子問題的最優(yōu)解，即問題具有最優(yōu)子結構的性質。在背包問題中，第一次選擇單位質量最大的貨物，它是第一個子問題的最優(yōu)解，第二次選擇剩下的貨物中單位重量價值最大的貨物，同樣是第二個子問題的最優(yōu)解，依次類推。其次，如何選擇一個貪心標準？正確的貪心標準可以得到問題的最優(yōu)解，在確定采用貪心策略解決問題時，不能隨意的判斷貪心標準是否正確，尤其不要被表面上看似正確的貪心標準所迷惑。在得出貪心標準之后應給予嚴格的數學證明。下面來看看0

13、-1背包問題。給定一個最大載重量為M的卡車和N種動物。已知第i種動物的重量為W,其最大價值i為V,設定M,W，V均為整數，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價111值最大。分析：對于N種動物，要么被裝，要么不裝，也就是說在滿足卡車載重的條件下，如何選擇動物，使得動物價值最大的問題。即確定一組XI,X2,，Xn,XiG0,1f(x)=max(工X*V)其中，工(X*W)WWiiii從直觀上來看，我們可以按照上例一樣選擇那些價值大，而重量輕的動物。也就是可以按價值質量比(V/W)的大小來進行選擇。可以看出，每做一次選擇，都是從剩下的動物中ii選擇那些V/W最大的，這種局部最優(yōu)的選擇是

14、否能滿足全局最優(yōu)呢？我們來看看一個簡單ii的例子：設N=3，卡車最大載重量是100,三種動物A、B、C的重量分別是40,50,70,其對應的總價值分別是80、100、150。情況A：按照上述思路，三種動物的V/W分別為2,2,2.14。顯然，我們首先選擇動物C,ii得到價值150,然后任意選擇A或B,由于卡車最大載重為100,因此卡車不能裝載其他動物。情況B不按上述約束條件，直接選擇A和B?？梢缘玫絻r值80+100=180，卡車裝載的重量為40+50=90。沒有超過卡車的實際載重，因此也是一種可行解，顯然，這種解比上一種解要優(yōu)化。問題出現在什么地方呢？我們看看圖2-18價值150價值190圖2

15、3卡車裝載貨物情況分析從圖23中明顯可以看出，情況A,卡車的空載率比情況B高。也就是說，上面的分析，只考慮了貨物的價值質量比，而沒有考慮到卡車的運營效率，因此，局部的最優(yōu)化，不能導致全局的最優(yōu)化。因此，貪心不能簡單進行，而需要全面的考慮，最后得到證明。例26排隊打水問題有N個人排隊到R個水龍頭去打水，他們裝滿水桶的時間為T1,T2,，Tn為整數且各不相等，應如何安排他們的打水順序才能使他們花費的時間最少？分析：由于排隊時，越靠前面的計算的次數越多，顯然越小的排在越前面得出的結果越小(可以用數學方法簡單證明，這里就不再贅述)，所以這道題可以用貪心法解答，基本步驟：(1)(2)(3)參考程序：將輸

16、入的時間按從小到大排序；將排序后的時間按順序依次放入每個水龍頭的隊列中；統計，輸出答案。ProgramExam26;ConstFinp二'Input.Txt'Fout二'Output.Txt'VarASN,MMinProcedureInit;VarIBegin:Array1.100OfInteger;:Array1.100OfLongint;:Integer;:Longint;讀入數據:Integer;Assign(Input,Finp);Reset(Input);Readln(N,M);ForI:=1ToNDoRead(AI);Close(Input);End

17、;ProcedureSort(L,R:Integer);將時間從小到大排序VarI,J,X,Y:Integer;BeginI:=L;J:=R;X:=A(L+R)Div2;RepeatWhile(AI<=X)And(I<R)DoInc(I);While(AJ>=X)And(J>L)DoDec(J);IfI<=JThenBeginY:=AI;AI:=AJ;AJ:=Y;Inc(I);Dec(J);End;UntilI>J;IfL<JThenSort(L,J);IfR>IThenSort(I,R);End;ProcedureWork;VarI,J,K:I

18、nteger;BeginFillchar(S,Sizeof(S),0);J:=0;Min:=0;ForI:=1ToNDo用貪心法求解BeginInc(J);IfJ=M+1ThenJ:=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.均分紙牌有N堆紙牌，編號分別為1,2,N。每堆上有若干張，但紙牌總數必為N的倍數?？梢栽谌我欢焉先∪粲趶埣埮疲缓笠苿?。移牌規(guī)則為：在編號為1堆上取的紙牌

19、，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F在要求找出一種移動方法，用最少的移動次數使每堆上紙牌數都一樣多。例如N=4,4堆紙牌數分別為：98176移動3次可達到目的：從取4張牌放到(981310)->從取3張牌放到(9111010)->從取1張牌放到(10101010)。輸入格式N(N堆紙牌，1<=N<=100)A1A2.An(N堆紙牌，每堆紙牌初始數，lv=Ai<=10000輸出格式OutputFormat所有堆均達到相等時的最少移動次數。樣例輸入498176樣例輸出3題解：

20、programzzh;vara:array1.99ofinteger;b,c,d,e,f,g,n,i:integer;beginread(n);c:=0;forb:=1tondoread(ab);forb:=1tondoc:=c+ab;d:=cdivn;ifcmodn=0thenbeginfore:=lton-1doifdv>aethenbeginae+1:=ae+1+ae-d;ae:=d;f:=f+1;end;write(f);end;end.金銀島描述某天KID利用飛行器飛到了一個金銀島上，上面有許多珍貴的金屬，KID雖然更喜歡各種寶石的藝術品，可是也不拒絕這樣珍貴的金屬。但是他只帶

21、著一個口袋，口袋至多只能裝重量為w的物品。島上金屬有s個種類，每種金屬重量不同，分別為n】,n2，ns，同時每個種類的金屬總的價值也不同，分別為V,v2vs。KID想一次帶走價值盡可能多的金屬，問他最多能帶走價值多少的金屬。注意到金屬是可以被任意分割的，并且金屬的價值和其重量成正比。輸入第1行是測試數據的組數k，后面跟著k組輸入。每組測試數據占3行，第1行是一個正整數w(1<=w<=10000)，表示口袋承重上限。第2行是一個正整數s(1<=s<=100)表示金屬種類。第3行有2s個正整數分別為n】,v】,n2,v2ns,vs分別為第一種，第二種，第s種金屬的總重量和總

22、價值(1<=ni<=10000,1<=v<=10000)。輸出k行，每行輸出對應一個輸入。輸出應精確到小數點后2位。樣例輸入5o1010050307348710010000514343323354543548743樣例輸出171.93508.00貪心題目，先算出每種金屬單價d,按照d進行排序，然后貪心地揀前面幾個，直到背包滿。vara,b:array0.100oflongint;p:array0.100ofreal;n,i,j,k,s,m,g:longint;tot:real;proceduresort(l,r:longint);vari,j,y:longint;x,t

23、t:real;begini:=l;j:=r;x:=p(l+r)div2;repeatwhilepi<xdoinc(i);whilex<pjdodec(j);ifnot(i>j)thenbegintt:=pi;pi:=pj;pj:=tt;y:=ai;ai:=aj;aj:=y;y:=bi;bi:=bj;bj:=y;inc(i);j:=j-1;end;untili>j;ifl<jthensort(l,j);ifi<rthensort(i,r);end;beginreadln(k);forg:=1tokdobeginreadln(m);readln(s);fori:

24、=1tosdobeginread(ai,bi);pi:=bi/ai;end;tot:=0;sort(1,s);i:=s;while(i>0)and(m>0)doifm>=aithenbegindec(m,ai);tot:=tot+bi;dec(i);endelsebegintot:=tot+m*pi;m:=0;end;writeln(tot:0:2);end;end.裝箱問題木千.查看提交統計提問總時間限制:1000ms內存限制:65536kB描述一個工廠制造的產品形狀都是長方體，它們的高度都是h,長和寬都相等，一共有六個型號，他們的長寬分別為1*1,2*2,3*3,4*4,

25、5*5,6*6。這些產品通常使用一個6*6*h的長方體包裹包裝然后郵寄給客戶。因為郵費很貴，所以工廠要想方設法的減小每個訂單運送時的包裹數量。他們很需要有一個好的程序幫他們解決這個問題從而節(jié)省費用?，F在這個程序由你來設計。輸入輸入文件包括幾行，每一行代表一個訂單。每個訂單里的一行包括六個整數，中間用空格隔開，分別為1*1至6*6這六種產品的數量。輸入文件將以6個0組成的一行結尾。輸出除了輸入的最后一行6個0以外，輸入文件里每一行對應著輸出文件的一行，每一行輸出一個整數代表對應的訂單所需的最小包裹數。樣例輸入004001751000000000樣例輸出2解題思路這個問題描述得比較清楚，在這里只解

26、釋一下輸入輸出樣例：共兩組有效輸入，第一組表示有4個3X3的產品和1個6X6的產品，此時4個3X3的產品占用一個箱子，另外1個6X6的產品占用一個箱子，所以箱子數是2；第二組表示有7個1X1的產品，5個2X2的產品和1個3X3的產品，可以把它們統統放在一個箱子中，所以輸出是1。分析6個型號的產品占用箱子的具體情況如下：6X6的產品每個會占用一個完整的箱子，并且沒有空余的空間；5X5的產品每個占用一個新的箱子，并且留下11個可以盛放1X1的產品的空余空間；4X4的產品每個占用一個新箱子，并且留下5個可以盛放2X2的產品的空余空間；3X3的產品比較復雜，首先3X3的產品不能放在原來盛放5X5或者4

27、X4的箱子中，那么必須為3X3的產品另開新的箱子，新開的箱子數目等于3X3的產品的數目除以4向上取整；同時需要討論為3X3的產品新開箱子時，剩余的空間可以盛放多少2X2和1X1的產品（這里如果空間可以盛放2X2的產品，就將它記入2X2的空余空間，等到2X2的產品全部裝完，如果還有2X2的空間剩余，再將它們轉換成1X1的剩余空間）。分情況討論為3X3的產品打開的新箱子額中剩余的空位，共為4種情況：第一種，3X3的產品的數目正好是4的倍數，所以沒有空余空間；第2種，3X3的產品數目是4的倍數加1,這時還剩5個2X2的空位和7個1X1的空位；第3種，3X3的產品數目是4的倍數加2,這時還剩3個2X2

28、的空位和6個1X1的空位；第4種，3X3的產品的數目是4的倍數加3,這時還剩1個2X2的空位和5個1X1的空位；處理完3X3的產品，就可以比較一下剩余的2X2的空位和2X2產品的數目，如果產品數目多，就將2x2的空位全部填滿，再為2x2的產品打開新箱子，同時計算新箱子中1x1的空位，如果剩余空位多，就將2x2的產品全部填入2x2的空位，再將剩余的2x2空位轉換成1x1的空位；最后處理1x1的產品，比較一下1x1的空位與1x1的產品數目，如果空位多，將1x1的產品全部填入空位，否則，先將1x1的空位填滿，然后再為1x1的產品打開新的箱子。vari,tt,ans,j:longint;a:array

29、0.6oflongint;f:array1.6,1.6,0.36oflongint;beginfori:=1to6doread(ai);f3,2,7:=1;f3,2,6:=1;f3,2,5:=1;whilea1+a2+a3+a4+a5+a6<>0dobeginans:=0;fori:=6downto1dowhileai>0dobegininc(ans);tt:=36-i*i;dec(ai);forj:=6-idownto1dobeginwhile(tt>=j*j)and(aj>0)and(fi,j,tt=0)dobegintt:=tt-j*j;dec(aj);en

30、d;end;end;writeln(ans);fori:=1to6doread(ai);end;end.例27:旅行家的預算（N0I99分區(qū)聯賽第3題）一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發(fā)時油箱時空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點每升汽油價格P和沿途加油站數N（N可以為零），油站i離出發(fā)點的距離Di、每升汽油價格Pi（i=1,2,N）。計算結果四舍五入至小數點后兩位。如果無法到達目的地，則輸出“NoSolution”樣例:InputD1=275.6C=11.9D2=27.4P=2.8N=2油站號I離出

31、發(fā)點的距離D,每升汽油價格P,1102.02.92220.02.2Output26.95（該數據表示最小費用）分析:需要考慮如下問題:1）出發(fā)前汽車的油箱是空的，故汽車必須在起點（1號站）處加油。加多少油？2）汽車行程到第幾站開始加油，加多少油？可以看出，原問題需要解決的是在哪些油站加油和加多少油的問題。對于某個油站，汽車加油后到達下一加油站，可以歸結為原問題的子問題。因此，原問題關鍵在于如何確定下一個加油站。通過分析，我們可以選擇這樣的貪心標準:對于加油站I,下一個加油站J可能第一個是比油站I油價便宜的油站，若不能到達這樣的油站，則至少需要到達下一個油站后，繼續(xù)進行考慮。對于第一種情況，則油

32、箱需要（d（j）-d（i）/m加侖汽油。對于第二種情況，則需將油箱加滿。貪心算法證明如下:設定如下變量:Valuei:第i個加油站的油價；Overi:在第i站時的剩油；Wayi:起點到油站i的距離；XI：X記錄問題的最優(yōu)解，XI記錄油站I的實際加油量。首先，Xl工0,0verl=0。假設第I站加的XI一直開到第K站。則有，XI.xk-l都為0,而XK工0。 若ValueIValuek,貝V按貪心方案，第I站應加油為T=（Wayk-WayI）/M-0verI。若T<XI，則汽車無法從起點到達第k個加油站；與假設矛盾。若TXI,則預示著，汽車開到油站K,仍然有油剩余。假設剩余W加侖汽油，則須

33、費用ValueI*W,如果W加侖汽油在油站K加，則須費用ValueK*W,顯然ValueK*W<ValueI*W。 若ValueIValuek,則按貪心規(guī)則，須加油為T=C-0verI（即加滿油）。若TXI，則表示在第I站的加油量會超過汽車的實際載油量，顯然是不可能的。若T>XI，則表示在第I站的不加滿油，而將一部分油留待第K站加，而ValueIValuek,所以這樣費用更高。綜合上述分析，可以得出如下算法：I:=1汽車出發(fā)設定為第1個加油站L:=C*D2；油箱裝滿油能行駛的距離repeat在L距離以內，向后找第一個油價比站便宜的加油站J；ifJ存在thenifI站剩余油能到達Jt

34、hen計算到達J站的剩油else在I站購買油，使汽車恰好能到達站else在I站加滿油；I：=J汽車到達丿站until汽車到達終點；程序如下：programNOI99L_3;constInp=input.txt'Outp=output.txt'MaxN=10001;Zero=1e-16;typeRectype=recordValue:Real;Way:Real;Over:Real;end;RecPtr二"Rectype;varOil:array1.D1,C,D2,最大油站數誤差值油站的數據結構油價距起點的距離汽車到達該站時的剩油N:Integer;Cost:Real;M

35、axWay,油站指針.MaxNofRecPtr;記錄所有油站起點到終點之間的距離汽車油箱的容量每升汽油能行駛的距離油站數最小油費滿油時汽車最大的行駛距離functioninit:Boolean;初始化，并判無解varI:Integer;beginRead(D1,C,D2);New(Oil1);處理初始值和起始油站Oill.Way:=0;Read(Oill.Value,n);MaxWay:=D2*C;forI:二2tondobegin讀入后NT個油站信息New(OilI);Readln(OilI.Way,OilI.Value);0ilI.over:=0;end;Inc(n);將終點也看成一個加油

36、站New(Oiln);Oiln.Way:=DI;Oiln.Value:=0;Oiln.over:=0;forI:=2ton+1do判是否無解if(OilI".Way-OilI-l".Way>MaxWay)thenbegininit:=False;Exit;end;init:=True;end;procedureBuy(I:Integer;Miles:Real);在I加油站購買Miles/D2加侖汽油beginCost:二Cost+Miles/D2*OilI.Value;將買汽油所需的費用加到Cost變量中end;procedureSolve;varI,J:Intege

37、r;S:Real;beginI:=1;汽車在起點repeatS:=0.0;在MaxWay范圍以內，找第一個油價比I站便宜的加油站Jwhile(S<=MaxWay+zero)and(J<=N-1)and(OilI.Value<=OilJ.Value)dobeginInc(J);S:=S+OilJ.Way-OilJ-l.Way;end;ifS<=MaxWay+zerothen如果找到J站或可以直達終點如果剩油足夠到達J站，則無需購油，并計算到達J站時汽車的剩油if(0ilI.0ver+Zero=0ilJ.Way-OilI.Way)then0ilJ.0ver:=0ilI.0v

38、er-OilJ.Way+OilI.Wayelsebegin在I站購買恰好能到達J站的油量Buy(I,OilJ.Way-OilI.Way-0ilI.0ver);0ilJ.0ver:=0.0;endelsebegin附近無比I站便宜的加油站JBuy(I,MaxWay-0ilI.0ver);在I站加滿油J:=I+1;行駛到下一站0ilJ.0ver:二MaxWay-(0ilJ.Way-0ilI.Way);end;I:=J;untilI=N;end;汽車直達J站汽車到達終點beginCost:=0;Assign(Input,Inp);Reset(Input);Assign(0utput,0utp);Re

39、write(0utput);ifinitthenbeginSolve;Writeln(Cost:0:2);endelseWriteln(NoSolution');Close(Input);Close(0utput);end.主程序如果有解求解輸出最少費用輸出無解例28：兩機器加工問題有n個部件需在A,B機器上加工，每個工件都必須經過先A后B兩道工序。已知：部件i在A、B機器上的加工時間分別為a,b。ii問：如何安排n個工件的加工順序，才能使得總加工時間最短？輸入示例：N=5工件I12345a.358710b62149輸出示例：34（最少時間）15423（最優(yōu)加工順序）分析：本題求一個加

40、工順序使得加工總時間最短，要使時間最短，則就是讓機器的空閑時間最短。一旦A機器開始加工，則A機器將會不停的進行作業(yè)，關鍵是B機器在加工過程中，有可能要等待A機器。很明顯第一個部件在A機器上加工時，B機器必須等待，最后一個部件在B機器上加工，A機器也在等待B機器的完工?？梢源竽懖孪?，要使總的空閑的最少，就要把在A機器上加工時間最短的部件最先加工，這樣使得B機器能以最快的速度開始加工;把在B機器上加工時間最短的部件放在最后加工。這樣使得A機器能盡快的等待B機器完工。于是我們可以設計出這樣的貪心法：設M=mina,biii將M按照從小到大的順序排序。然后從第1個開始處理，若M=a,則將它排在從頭開始

41、ii的已經作業(yè)后面，若M=b，則將它排在從尾開始的作業(yè)前面。ii例如：N=5（a1，a2，a3，a4，a5）=（3，5，8，7，10）（b，b，b，b，b）=（6，2，1，4，9）12345貝J（m，m，m，m，m）=（3，2，1，4，9）12345排序之后為（m3,m2,mi，m4,叫）處理m：Vm=b/.m排在后面；加入m之后的加工順序為（，3）；3 3333處理m：Vm=b/.m排在后面；加入m之后的加工順序為（，2,3）；22222處理m：Vm=a/m排在前面；加入m之后的加工順序為（1,2,3）；13111處理m：Vm=b/m排在后面；加入m之后的加工順序為（1,4,2,3）；4 4

42、444處理m：Vm=b/m排在后面；加入m之后的加工順序為（1,5,4,2,3）；5 5555則最優(yōu)加工順序就是（1，5，4，2，3），最短時間為34。顯然這是最優(yōu)解。問題是這種貪心策略是否正確呢？還需證明。證明過程如下：設S=J,J,J,為待加工部件的作業(yè)排序，若A機器開始加工S中的部件時，12nB機器還在加工其它部件，t時刻后再可利用，在這樣的條件下，加工S中任務所需的最短時間T（S,t）二mina+T（S-J,b+maxt-a,O）其中，JWS。iiiiiaig機器t1biE機器一Ijm=aimaxjt-on,u|-umiiiAdL.E機器.亠J:一(b)t.>rt±mo

43、x|t-an,u|t-an圖24機器加工作業(yè)示意圖從圖24可以看出，(a)為作業(yè)I等待機器B的情況，(b)為機器B等待作業(yè)I在機器A上完成的情形。假設最佳的方案中，先加工作業(yè)J,然后加工作業(yè)J,則有：ijT(S,t)=a+T(S-J,b+Maxt_a,0)iiii=a+a+T(S-J,J,b+maxb+maxta,0-a,0)ijijjiij=a+a+T(S-J.,J.,T.)iJiJjT=b+maxb+maxta,0a,0ijjiij=b+ba+maxmaxta,0,abjijiji=b+ba+maxta,ab,0ijjiji=b+baa+maxt,a,a+abijijiijiiji=<b+b-a,ijjb,t+b+b-a-a,若maxt,a.,a+a.-b.=tiiji若maxt,a,a+ab=aiijii若maxt,a,a+ab=a+abiijiiji若將作業(yè)J和作業(yè)J的加工順序，則有：ijT'(S,t)=a+a+T