1、第第12章章 貪心法貪心法與動態規劃與動態規劃12.1 12.1 貪貪 心心 法法12.2 12.2 動動 態態 規規 劃劃問題：問題：假設有面值為假設有面值為5元、元、2元、元、1元、元、5角、角、2角、角、1角的貨幣，需要角的貨幣，需要找給顧客找給顧客4元元6角現金，為使付出角現金，為使付出的貨幣的數量最少，應如何找零？的貨幣的數量最少，應如何找零？找零問題找零問題解決方法：解決方法：l首先選出首先選出1張面值不超過張面值不超過4元元6角的最大面值的貨角的最大面值的貨幣，即幣，即2元；元；l再選出再選出1張面值不超過張面值不超過2元元6角的最大面值的貨幣，角的最大面值的貨幣，即即2元；元；

2、l再選出再選出1張面值不超過張面值不超過6角的最大面值的貨幣，即角的最大面值的貨幣，即5角；角；l再選出再選出1張面值不超過張面值不超過1角的最大面值的貨幣，即角的最大面值的貨幣，即1角；角；總共付出總共付出4張貨幣。張貨幣。找零問題找零問題這就是貪心選擇！找零問題中的貪心找零問題中的貪心l 在付款問題每一步的貪心選擇中，在不超過應付款在付款問題每一步的貪心選擇中，在不超過應付款金額的條件下，只選擇面值最大的貨幣，而不去考慮金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且它還不會改變決在后面看來這種選擇是否合理，而且它還不會改變決定：一旦選出了一張貨幣，就永遠選定

3、。定：一旦選出了一張貨幣，就永遠選定。l 付款問題的貪心選擇策略是盡可能使付出的貨幣最付款問題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數最慢快地滿足支付要求，其目的是使付出的貨幣張數最慢地增加，這正體現了貪心法的設計思想。地增加，這正體現了貪心法的設計思想。貪心法的思想貪心法的思想 在實際生活中，經常會遇到類似求一個問題的在實際生活中，經常會遇到類似求一個問題的可行解和最優解的要求，這就是所謂的最優化可行解和最優解的要求，這就是所謂的最優化問題。每個最優化問題都包含一組限制條件和問題。每個最優化問題都包含一組限制條件和一個優化函數，符合限制條件的問題求解方案

4、一個優化函數，符合限制條件的問題求解方案稱為可行解，使優化函數取得最佳值的可行解稱為可行解，使優化函數取得最佳值的可行解稱為最優解。稱為最優解。貪心法的思想貪心法的思想 貪心法是求解這類問題最優解的一種常用算法：貪心法是求解這類問題最優解的一種常用算法： 它從問題的某個初始解出發，采用逐步構造最優解的它從問題的某個初始解出發，采用逐步構造最優解的方法向給定的目標推進。方法向給定的目標推進。 在每個局部階段，都做出一個看上去最優的決策（即在每個局部階段，都做出一個看上去最優的決策（即某種意義下的、或某個標準下的局部最優解），并期某種意義下的、或某個標準下的局部最優解），并期望通過每次所做的的局部

5、最優選擇產生出一個全局最望通過每次所做的的局部最優選擇產生出一個全局最優解。優解。 做出貪心決策的依據稱為貪心準則（策略），決策一做出貪心決策的依據稱為貪心準則（策略），決策一旦做出，就不可再更改。旦做出，就不可再更改。 貪心與遞推的不同之處：貪心推進的每一步不是依據貪心與遞推的不同之處：貪心推進的每一步不是依據某一固定的遞推式，而是做一個當時看似最佳的貪心某一固定的遞推式，而是做一個當時看似最佳的貪心選擇（操作），不斷地將問題實例歸納為更小的相似選擇（操作），不斷地將問題實例歸納為更小的相似問題。貪心準則是正確解決貪心問題的關鍵。問題。貪心準則是正確解決貪心問題的關鍵。 貪心法的基本思路：貪

6、心法的基本思路：（1 1）建立數學模型來描述問題；）建立數學模型來描述問題；（2 2）把求解的問題分成若干個子問題；）把求解的問題分成若干個子問題；（3 3）對每一子問題求解，得到子問題的局部最優解。）對每一子問題求解，得到子問題的局部最優解。（4 4）把子問題的解局部最優解合成原來解問題的一個解）把子問題的解局部最優解合成原來解問題的一個解。 【例例12.112.1】刪數問題刪數問題 鍵盤輸入一個高精度的正整數鍵盤輸入一個高精度的正整數n n（ 100100位），去掉其位），去掉其中任意中任意s s個數字后剩下的數字按照原來的左右次序組成個數字后剩下的數字按照原來的左右次序組成一個新的正整數

7、。編程對給定的一個新的正整數。編程對給定的n n與與s s，尋找一種方案，尋找一種方案，使得剩下的數字組成的新數最小。，使得剩下的數字組成的新數最小。 比如：比如：n=178543n=178543，s=4s=4 則輸出則輸出 13 13 ，表示正整數，表示正整數178543178543，刪除，刪除4 4位數字后得位數字后得到的最小值是到的最小值是 1313。 （1 1）由于給定的正整數有效位數是）由于給定的正整數有效位數是100100位，位，用一般的整數類型（包括長整數）無法表示，用一般的整數類型（包括長整數）無法表示，可以考慮用字符串來存儲正整數?？梢钥紤]用字符串來存儲正整數。 （2 2）如

8、何決定哪）如何決定哪s s位數字被刪除呢？被刪除的位數字被刪除呢？被刪除的是否是最大的是否是最大的s s個數字呢？為了盡可能逼近目個數字呢？為了盡可能逼近目標，采用貪心法來解決問題，標，采用貪心法來解決問題，選取的貪心策略為：選取的貪心策略為： 把對把對s s個數字的刪除，看成是一個逐步實現的過程，個數字的刪除，看成是一個逐步實現的過程，每一步刪除一個數字，用每一步刪除一個數字，用s s步完成對步完成對s s個數字的刪除。個數字的刪除。 每一步總是選擇一個使剩下的數最小的數字完成刪每一步總是選擇一個使剩下的數最小的數字完成刪除，也就是按照從高位到低位的順序進行搜索，如果除，也就是按照從高位到低

9、位的順序進行搜索，如果各位數字式遞增的，則刪除最后一位數字；否則，刪各位數字式遞增的，則刪除最后一位數字；否則，刪除第一個遞減區間的首位數字。這樣選擇一位數字并除第一個遞減區間的首位數字。這樣選擇一位數字并刪除后，便得到一個新的數字串。刪除后，便得到一個新的數字串。 以后每一步回到上一步完成刪除之后的數字串的串以后每一步回到上一步完成刪除之后的數字串的串首，按照上述規則再刪除下一個數字。執行首，按照上述規則再刪除下一個數字。執行s s次后，便次后，便刪除了刪除了s s位數字，剩余的數字串便是問題的解。位數字，剩余的數字串便是問題的解。 例如：例如：n=178543n=178543，s=4s=4

10、時的刪除過程為：時的刪除過程為： 第一步：第一步：n=17n=1785438543，第一個遞減區間為，第一個遞減區間為85438543，刪，刪除其首位數字除其首位數字8 8； 第二步：第二步：n=1n=175437543，第一個遞減區間為，第一個遞減區間為75437543，刪除，刪除其首位數字其首位數字7 7； 第三步：第三步：n=1n=1543543，第一個遞減區間為，第一個遞減區間為543543，刪除其，刪除其首位數字首位數字5 5； 第四步：第四步：n=1n=14343，第一個遞減區間為，第一個遞減區間為4343，刪除其首位，刪除其首位數字數字4 4； 剩余的數字串為：剩余的數字串為：1

11、313，即為所求。，即為所求。#include stdio.h#include stdio.h#include string.h#include string.hint main()int main() int i,s,len;int i,s,len;char a100;char a100;scanf(%s,a);scanf(%s,a);scanf(%d,&s);scanf(%d,&s);while(s0)while(s0) i=0;i=0;len=strlen(a);len=strlen(a);while(ilen &ai=ai+1)while(ilen &a

12、i=ai+1)i+;i+;while(ilen)while(ilen) ai=ai+1;ai=ai+1;i+;i+; s-;s-; printf(%sn,a);printf(%sn,a);return 0;return 0; 【例例12.212.2】 事件序列問題事件序列問題-活動選擇問題活動選擇問題參考資料：參考資料：http:/ 0# 1# 2# 3# 4# 5# 6# 7# 8# 9# 10#11#發生時刻 1303256410 81515結束時刻 3478910 12 14 15 18 1920 已知已知N=12N=12個事件的發生時刻和結束時刻（見下表，其個事件的發生時刻和結束時刻（

13、見下表，其中事件已經按結束時刻升序排序）。一些在時間上沒有中事件已經按結束時刻升序排序）。一些在時間上沒有重疊的事件，可以構成一個事件序列，如事件重疊的事件，可以構成一個事件序列，如事件2 2，8 8和和1010，可以寫成序列，可以寫成序列22，8 8，1010。事件序列包含的事件。事件序列包含的事件數目，稱為事件序列的長度。請編程找出一個最長的事數目，稱為事件序列的長度。請編程找出一個最長的事件序列。件序列。各事件在時間上的占用情況012345678910111213141516171819200#1#2#3#4#5#6#7#8#9#10#11#2，8，10序列不是最長的序列0，1，7，10

14、更長一些 如何選擇事件，可以保證得到最長的事件序列呢？ 用用beginibegini表示事件表示事件i i的發生時刻，用的發生時刻，用endiendi表示事件表示事件i i的的結束時刻。結束時刻。 如果兩個事件如果兩個事件a a，b b（a ab b）在時間上沒有重疊，那么有）在時間上沒有重疊，那么有 endabeginbendabeginb； 如果滿足這個條件，則兩個事件在時間上一定沒有重疊如果滿足這個條件，則兩個事件在時間上一定沒有重疊，這是一個，這是一個充分必要充分必要條件。條件。 原題的要求其實就是找到一個最長的序列原題的要求其實就是找到一個最長的序列a a1 1a a2 2a an

15、n，滿足：，滿足： begina begina1 1 endaenda1 1beginabegina2 2 endaenda2 2 beginabeginan nendaendan n 本題目的貪心策略：即為了得到當前情況下最優的一本題目的貪心策略：即為了得到當前情況下最優的一個結果，可以在當前可選的事件中選取編號最小的那個結果，可以在當前可選的事件中選取編號最小的那個進入序列，也就是選取最早結束的那個事件進入序個進入序列，也就是選取最早結束的那個事件進入序列。即：列。即： 第一個要選取的事件是最早結束的事件；第一個要選取的事件是最早結束的事件； 下一個要選取的事件，必須是上一個選取的事件結束

16、下一個要選取的事件，必須是上一個選取的事件結束之后開始的事件中最早結束的事件；之后開始的事件中最早結束的事件； 在程序中設置一個在程序中設置一個selectiselecti標記數組，表示事件標記數組，表示事件i i是否是否要選入序列，選入時值為要選入序列，選入時值為1 1，否則值為，否則值為0 0。 #include stdio.h#include stdio.h#define N 12#define N 12void outputresult(int select,int n)void outputresult(int select,int n) int i;int i;printf(0);

17、printf(0);for(i=1;in;i+)for(i=1;in;i+)if(selecti=1)if(selecti=1)printf(,%d,i);printf(,%d,i);printf(n);printf(n); int main()int main() char beginN=1,3,0,3,2,5,6,4,10,8,15,15;char beginN=1,3,0,3,2,5,6,4,10,8,15,15;int endN=3,4,7,8,9,10,12,14,15,18,19,20;int endN=3,4,7,8,9,10,12,14,15,18,19,20;int sele

18、ctN=0;int selectN=0;int i=0;int i=0;int timestart=0;int timestart=0;while(iN)while(i=timestart)if (begini=timestart) selecti=1;selecti=1;timestart=endi;timestart=endi; i+;i+; outputresult(select,N);outputresult(select,N);return 0;return 0; 【例【例12.312.3】 區間覆蓋問題區間覆蓋問題【例例12.312.3】 區間覆蓋問題區間覆蓋問題例如例如M=5M=

19、5，整數，整數1 1、3 3、4 4、8 8和和1111表示區間表示區間，要求所用，要求所用線段不超過線段不超過N=3N=3條條。118431f1：f2：f3：f4：01234567891011M=56788Totallength方案方案f4正是這個任務的答案正是這個任務的答案 用用i i來表示來表示x x坐標軸上坐標為坐標軸上坐標為i-1i-1，i i的的長度為長度為1 1的區間的區間，并給出，并給出M(1M200)M(1M200)個不同的整數，表示個不同的整數，表示MM個這樣的區間個這樣的區間。現在要求。現在要求畫幾畫幾條線段覆蓋住所有的區間條線段覆蓋住所有的區間，條件是：每條線段可以任意

20、長，但是要求，條件是：每條線段可以任意長，但是要求所畫所畫線段的長度之和最小線段的長度之和最小，并且線段的，并且線段的數目不超過數目不超過NN(1N50)(1N50)。設置一個整型數組設置一個整型數組positionMpositionM來表示所有的區間，假設來表示所有的區間，假設positionMpositionM已經按從小到大的順序排好。已經按從小到大的順序排好。如果如果NMNM，那么用，那么用MM條長度為條長度為1 1的線段可以覆蓋住所有的的線段可以覆蓋住所有的區間，所求的線段總長為區間，所求的線段總長為MM。如果如果NNMM，顯然，顯然MM1,1,可以按照如下的貪心策略來解決：可以按照如

21、下的貪心策略來解決： 0 01 12 23 34 4134811position11843101234567891011M=5如果如果N=1N=1，即要用一條線段覆蓋住所有區間，即要用一條線段覆蓋住所有區間，很顯然所需線段總長即為很顯然所需線段總長即為positionM-1-positionM-1-position0+1position0+1。圖圖12.3 N=1條線段覆蓋所有條線段覆蓋所有區區間間position012M-1N=1 如果如果N=2N=2，即要用兩條線段覆蓋住所有區間，相當于，即要用兩條線段覆蓋住所有區間，相當于把把N=1N=1中的線段分為兩部分，各覆蓋住左邊與右邊的區中的線段

22、分為兩部分，各覆蓋住左邊與右邊的區間。間。 如果線段在如果線段在MM個區間中不相鄰的區間之間斷開（如在個區間中不相鄰的區間之間斷開（如在position0position0與與position1position1之間），左右兩段線段的端之間），左右兩段線段的端點可調整到坐標點可調整到坐標position0+1position0+1與與position1position1處，這處，這樣總長度小于斷開之前。樣總長度小于斷開之前。position012M-1N=2N=1線段長度減少線段長度減少:position1-(position0+1)。圖中兩條線段長度之和，比圖中兩條線段長度之和，比 原來一條

23、線段長度減少了原來一條線段長度減少了position1position1和和position0+1position0+1之間的距離，即：之間的距離，即： position1-position0-1 position1-position0-1。題目要求最小線段總長，可以找間隔最大的兩個相鄰區間，在它題目要求最小線段總長，可以找間隔最大的兩個相鄰區間，在它們之間斷開就可以了。這一過程相當于找們之間斷開就可以了。這一過程相當于找 distancei=positioni-positioni-1-1 distancei=positioni-positioni-1-1 (1 (1i iM)M)的最大值。的

24、最大值。 0 01 12 23 34 4134811position11843101234567891011M=51 10 03 32 2distance如果如果N=3N=3，相當于在，相當于在N=2N=2的方案下，將某條的方案下，將某條線段斷成兩截，并作可能的端點調整。線段斷成兩截，并作可能的端點調整。顯然，為了得到當前情況下最小的總長度，顯然，為了得到當前情況下最小的總長度，同樣應該在間隔最大的兩個相鄰區間之間斷同樣應該在間隔最大的兩個相鄰區間之間斷開。開。如果原來的方案是如果原來的方案是N=2N=2時總長最小的方案，時總長最小的方案，這一操作可以得到這一操作可以得到N=3N=3時總長最小

25、的方案。時總長最小的方案。當當N=kN=k（k k1 1）時依此類推，只需在）時依此類推，只需在N=k-1N=k-1時最小總長的覆蓋方案下，找到被同一條線時最小總長的覆蓋方案下，找到被同一條線段覆蓋的間隔最大的兩個相鄰區間，段覆蓋的間隔最大的兩個相鄰區間，“貪心貪心”地從間隔處斷開并適當調整兩邊線段的端地從間隔處斷開并適當調整兩邊線段的端點，就可以得到這是總長最小的方案。點，就可以得到這是總長最小的方案。#include #include #define N 200 / #define N 200 / 區間數目的上限區間數目的上限void sort1(int value,int n) / vo

26、id sort1(int value,int n) / 排序函數（非遞增）排序函數（非遞增） int i,j,t;int i,j,t;for(i=0;in-1;i+)for(i=0;in-1;i+)for(j=0;jn-1-i;j+)for(j=0;jn-1-i;j+)if(valuejvaluej+1)if(valuejvaluej+1) t=valuej;t=valuej;valuej=valuej+1;valuej=valuej+1;valuej+1=t;valuej+1=t; int main()int main() int m,i,n; / mint m,i,n; / m是要覆蓋的區

27、間數，是要覆蓋的區間數，n n是可用于覆蓋的線段數是可用于覆蓋的線段數int positionN; / int positionN; / 各個要覆蓋的區間各個要覆蓋的區間int distanceN-1; / int distanceN-1; / 存放相鄰區間的距離存放相鄰區間的距離printf(printf(請輸入要覆蓋的區間數請輸入要覆蓋的區間數m= );m= );scanf(%d,&m); / scanf(%d,&m); / 輸入要覆蓋的區間數輸入要覆蓋的區間數printf(printf(請輸入請輸入 %d %d 個要覆蓋的區間：個要覆蓋的區間： ,m);,m);for(i

28、=0;im;i+)for(i=0;im;i+)scanf(%d,&positioni); / scanf(%d,&positioni); / 輸入輸入mm個區間個區間sort1(position,m); / msort1(position,m); / m個區間降序排列個區間降序排列for(i=0;im-1;i+)for(i=0;i=m)if(n=m) printf(printf(最小的線段總長為：最小的線段總長為：%dn,m);%dn,m);return 0;return 0; int nline=1; / int nline=1; / 當前情況下所用線段總數當前情況下所用線段

29、總數int totallength=position0-positionm-1+1;int totallength=position0-positionm-1+1; / / 當前情況下所用線段總長當前情況下所用線段總長int devide=0; / int devide=0; / 當前最大的未斷開的區間距離當前最大的未斷開的區間距離while(nlinen)& / while(nline0) / (distancedevide0) / 還有不相鄰的區間還有不相鄰的區間 nline+; / nline+; / 再用一條線段再用一條線段totallength-=distancedevide

30、; / totallength-=distancedevide; / 總長減少總長減少devide+; / devide+; / 覆蓋該區間的線段斷開，指向下一最大間隔覆蓋該區間的線段斷開，指向下一最大間隔 printf(printf(最小線段總長為：最小線段總長為：%dn,totallength);%dn,totallength);return 0;return 0; 118431n=101234567891011M=56811Totallengthn=2n=312.1.3貪心法解題的一般步驟 上面三個任務所用的算法由一個共同點，就是在求最上面三個任務所用的算法由一個共同點，就是在求最優解的過程中，每一步都采用一種局部最優的策略，優解的過程中，每一步都采用一種局部最優的策略，把問