1、第六章第六章 貪心算法貪心算法 若在求解一個問題時，能根據每次所得到的局部最優解，推導出全局最若在求解一個問題時，能根據每次所得到的局部最優解，推導出全局最優或最優目標。那么，我們可以根據這個策略，每次得到局部最優解答，逐優或最優目標。那么，我們可以根據這個策略，每次得到局部最優解答，逐步而推導出問題，這種策略稱為步而推導出問題，這種策略稱為貪心法貪心法。下面我們看一些簡單例題。下面我們看一些簡單例題。【例例1】在在N行行M列的正整數矩陣中，要求從每行中選出列的正整數矩陣中，要求從每行中選出1個數，使得選出的總共個數，使得選出的總共N個個數的和最大。數的和最大。【算法分析算法分析】 要使總和最

2、大，則每個數要盡可能大，自然應該選每行中最大的那個數。因此，要使總和最大，則每個數要盡可能大，自然應該選每行中最大的那個數。因此，我們設計出如下算法我們設計出如下算法:讀入讀入N, M,矩陣數據；矩陣數據；Total := 0;For I := 1 to N do begin /對對N行進行選擇行進行選擇 選擇第選擇第I行最大的數行最大的數,記為記為K； Total := Total + K；End；輸出最大總和輸出最大總和Total； 從上例中我們可以看出，和遞推法相仿，貪心法也是從問題的某一個初始解出發，從上例中我們可以看出，和遞推法相仿，貪心法也是從問題的某一個初始解出發，向給定的目標遞

3、推。但不同的是，推進的每一步不是依據某一固定的遞推式，而是做向給定的目標遞推。但不同的是，推進的每一步不是依據某一固定的遞推式，而是做一個局部的最優選擇，即貪心選擇（在例中，這種貪心選擇表現為選擇一行中的最大一個局部的最優選擇，即貪心選擇（在例中，這種貪心選擇表現為選擇一行中的最大整數），這樣，不斷的將問題歸納為若干相似的子問題，最終產生出一個全局最優解。整數），這樣，不斷的將問題歸納為若干相似的子問題，最終產生出一個全局最優解。 特別注意的是，局部貪心的選擇是否可以得出全局最優是能否采用貪心法的關鍵特別注意的是，局部貪心的選擇是否可以得出全局最優是能否采用貪心法的關鍵所在。對于能否使用貪心策

4、略，應從理論上予以證明。下面我們看看另一個問題。所在。對于能否使用貪心策略，應從理論上予以證明。下面我們看看另一個問題。【例例2】部分背包問題部分背包問題 給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價值為Vi元/公斤，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大。【算法分析算法分析】 因為每一個物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優滿足全局最優，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進行排列，然后用循環從單位塊收益最大的取起，直到不能取為止便得到了最優解。 因此我們非常容易設計

5、出如下算法：問題初始化； /讀入數據按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 N) 在解決上述問題的過程中，首先根據題設條件，找到了貪心選擇標準(Vi)，并依據這個標準直接逐步去求最優解，這種解題策略被稱為貪心法。 因此，利用貪心策略解題，需要解決兩個問題：因此，利用貪心策略解題，需要解決兩個問題： 首先，確定問題是否能用貪心策

6、略求解；一般來說，適用于貪心策略首先，確定問題是否能用貪心策略求解；一般來說，適用于貪心策略求解的問題具有以下特點：求解的問題具有以下特點： 可通過局部的貪心選擇來達到問題的全局最優解。運用貪心策略解可通過局部的貪心選擇來達到問題的全局最優解。運用貪心策略解題，一般來說需要一步步的進行多次的貪心選擇。在經過一次貪心選擇之題，一般來說需要一步步的進行多次的貪心選擇。在經過一次貪心選擇之后，原問題將變成一個相似的，但規模更小的問題，而后的每一步都是當后，原問題將變成一個相似的，但規模更小的問題，而后的每一步都是當前看似最佳的選擇，且每一個選擇都僅做一次。前看似最佳的選擇，且每一個選擇都僅做一次。

7、原問題的最優解包含子問題的最優解，即問題具有最優子結構的性原問題的最優解包含子問題的最優解，即問題具有最優子結構的性質。在背包問題中，第一次選擇單位重量價值最大的貨物，它是第一個子質。在背包問題中，第一次選擇單位重量價值最大的貨物，它是第一個子問題的最優解，第二次選擇剩下的貨物中單位重量價值最大的貨物，同樣問題的最優解，第二次選擇剩下的貨物中單位重量價值最大的貨物，同樣是第二個子問題的最優解，依次類推。是第二個子問題的最優解，依次類推。 其次，如何選擇一個貪心標準？正確的貪心標準可以得到問題的最其次，如何選擇一個貪心標準？正確的貪心標準可以得到問題的最優解，在確定采用貪心策略解決問題時，不能隨

8、意的判斷貪心標準是否正優解，在確定采用貪心策略解決問題時，不能隨意的判斷貪心標準是否正確，尤其不要被表面上看似正確的貪心標準所迷惑。在得出貪心標準之后確，尤其不要被表面上看似正確的貪心標準所迷惑。在得出貪心標準之后應給予嚴格的數學證明。應給予嚴格的數學證明。下面來看看0-1背包問題。 給定一個最大載重量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價值為Vi，設定M，Wi，Vi均為整數，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價值最大。【分析分析】對于N種動物，要么被裝，要么不裝，也就是說在滿足卡車載重的條件下，如何選擇動物，使得動物價值最大的問題。 即確定一組X1，X2，X

9、n， Xi0,1 f(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，由于卡車最大載重

10、為100，因此卡車不能裝載其他動物。 情況B：不按上述約束條件，直接選擇A和B。可以得到價值80+100=180，卡車裝載的重量為40+50=90。沒有超過卡車的實際載重，因此也是一種可行解，顯然，這種解比上一種解要優化。 問題出現在什么地方呢？我們看看圖23 從圖23中明顯可以看出，情況A，卡車的空載率比情況B高。也就是說，上面的分析，只考慮了貨物的價值質量比，而沒有考慮到卡車的運營效率，因此，局部的最優化，不能導致全局的最優化。 因此，貪心不能簡單進行，而需要全面的考慮，最后得到證明。【例例3】排隊打水問題排隊打水問題 有N個人排隊到R個水龍頭去打水，他們裝滿水桶的時間為T1，T2，Tn為

11、整數且各不相等，應如何安排他們的打水順序才能使他們花費的時間最少？【算法分析算法分析】 由于排隊時，越靠前面的計算的次數越多，顯然越小的排在越前面得出的結果越小（可以用數學方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟： (1)將輸入的時間按從小到大排序； (2)將排序后的時間按順序依次放入每個水龍頭的隊列中； (3)統計，輸出答案。【樣例輸入樣例輸入】 4 2 /4人打水，2個水龍頭 2 6 4 5 /每個打水時間參考程序主要框架如下： read(n,r); Fillchar(S,Sizeof(S),0); J:=0; Min:=0; For I:=1 To N Do

12、/用貪心法求解 Begin Inc(J); If J=R+1 Then J:=1; SJ:=SJ+AI; Min:=Min+SJ; End; Writeln(Min); /輸出解答【樣例輸出】 23 /總共花費時間【例例4】均分紙牌（均分紙牌（NOIP2002） 有 N 堆紙牌，編號分別為 1，2，, N。每堆上有若干張，但紙牌總數必為 N 的倍數。可以在任一堆上取若干張紙牌，然后移動。 移牌規則為：在編號為 1 堆上取的紙牌，只能移到編號為 2 的堆上；在編號為 N 的堆上取的紙牌，只能移到編號為 N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。 現在要求找出一種移動方法，用

13、最少的移動次數使每堆上紙牌數都一樣多。例如 N=4，4 堆紙牌數分別為： 98176 移動3次可達到目的： 從 取4張牌放到（9 8 13 10）-從取3張牌放到 （9 11 10 10）- 從取1張牌放到（10 10 10 10）。【輸入格式】 N（N 堆紙牌，1 = N = 100） A1 A2 An （N 堆紙牌，每堆紙牌初始數，l= Ai =10000）【輸出格式】 所有堆均達到相等時的最少移動次數。【樣例輸入】Playcard.in 4 9 8 17 6 【樣例輸出】Playcard.out 3【算法分析算法分析】 如果你想到把每堆牌的張數減去平均張數，題目就變成移動正數，加到負數中

14、，使大家都變成0，那就意味著成功了一半！拿例題來說，平均張數為10,原張數9，8，17，6，變為-1，-2，7，-4，其中沒有為0的數，我們從左邊出發：要使第1堆的牌數-1變為0，只須將-1張牌移到它的右邊（第2堆）-2中；結果是-1變為0，-2變為-3，各堆牌張數變為0，-3，7，-4；同理：要使第2堆變為0，只需將-3移到它的右邊（第3堆）中去，各堆牌張數變為0，0，4，-4；要使第3堆變為0，只需將第3堆中的4移到它的右邊（第4堆）中去，結果為0，0，0，0，完成任務。每移動1次牌，步數加1。也許你要問，負數張牌怎么移，不違反題意嗎？其實從第i堆移動-m張牌到第i+1堆，等價于從第i+1

15、堆移動m張牌到第i堆，步數是一樣的。 如果張數中本來就有為0的，怎么辦呢？如0，-1，-5，6，還是從左算起（從右算起也完全一樣），第1堆是0，無需移牌，余下與上相同；再比如-1，-2，3，10，-4，-6，從左算起，第1次移動的結果為0，-3，3，10，-4，-6；第2次移動的結果為0，0，0，10，-4，-6，現在第3堆已經變為0了，可節省1步，余下繼續。參考程序主要框架如下：參考程序主要框架如下： ave:=0;step:=0; for i:=1 to n do begin read(ai); inc(ave,ai); /讀入各堆牌張數，求總張數讀入各堆牌張數，求總張數ave end;

16、ave:=ave div n; /求牌的平均張數求牌的平均張數ave for i:=1 to n do ai:=ai-ave; /每堆牌的張數減去平均數每堆牌的張數減去平均數 i:=1;j:=n; while (ai=0) and (i1) do dec(j); /過濾右邊的過濾右邊的0 while (ij) do begin inc(ai+1,ai); /將第將第i堆牌移到第堆牌移到第i+1堆中去堆中去 ai:=0; /第第i堆牌移走后變為堆牌移走后變為0 inc(step); /移牌步數計數移牌步數計數 inc(i); /對下一堆牌進行循環操作對下一堆牌進行循環操作 while (ai=0

17、) and (i0 do begin i：=1； /從串首開始找 while (ilength(n) and (ni1)and (n1=0) do delete(n，1，1)； 輸出n； /刪去串首可能產生的無用零【例例6】攔截導彈問題（攔截導彈問題（NOIP1999） 某國為了防御敵國的導彈襲擊，開發出一種導彈攔截系統，但是這種攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲，由于該系統還在試用階段。所以一套系統有可能不能攔截所有的導彈。 輸入導彈依次飛來的高度（雷達給出的高度不大于30000的正整數）。計算要

18、攔截所有導彈最小需要配備多少套這種導彈攔截系統。【輸入格式輸入格式】 n顆依次飛來的高度（1n1000）.【輸出格式輸出格式】 要攔截所有導彈最小配備的系統數k。【輸入樣例輸入樣例】missile.in 389 207 155 300 299 170 158 65【輸出樣例輸出樣例】missile.out 2【輸入輸出樣例輸入輸出樣例】輸入：導彈高度： 7 9 6 8 5輸出：導彈攔截系統K=2輸入：導彈高度： 4 3 2輸出：導彈攔截系統K=1【算法分析算法分析】 按照題意，被一套系統攔截的所有導彈中，最后一枚導彈的高度最低。設：k為當前配備的系統數； Lk為被第k套系統攔截的最后一枚導彈的高度，簡稱系統k的最低高度（1kn）。我們首先設導彈1被系統1所攔截（k1,Lk導彈1的高度）。然后依次分析導彈2，導彈n的高度。 若導彈i的高度高于所有系統的最低高度，則斷定導彈i不能被這些系統所攔截，應增設一套系統來攔截導彈I(kk+1,Lk導彈i的高度)；若導彈i低于某些系統的最低高度，那么導彈i均可被這些系統所攔截。究竟選擇哪個系統攔截可使得配備的系統數最少，我們不妨采用貪心策略，選擇其中最低高度最小（即導彈i的高度與系統最低高度最接近）的一套系統p(Lp=minLj|Lj