程序設(shè)計基礎(chǔ)12_1_貪心法

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

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

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

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

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

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

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

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

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

10、時的刪除過程為：時的刪除過程為： 第一步：第一步：n=17n=1785438543，第一個遞減區(qū)間為，第一個遞減區(qū)間為85438543，刪，刪除其首位數(shù)字除其首位數(shù)字8 8； 第二步：第二步：n=1n=175437543，第一個遞減區(qū)間為，第一個遞減區(qū)間為75437543，刪除，刪除其首位數(shù)字其首位數(shù)字7 7； 第三步：第三步：n=1n=1543543，第一個遞減區(qū)間為，第一個遞減區(qū)間為543543，刪除其，刪除其首位數(shù)字首位數(shù)字5 5； 第四步：第四步：n=1n=14343，第一個遞減區(qū)間為，第一個遞減區(qū)間為4343，刪除其首位，刪除其首位數(shù)字數(shù)字4 4； 剩余的數(shù)字串為：剩余的數(shù)字串為：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#發(fā)生時刻 1303256410 81515結(jié)束時刻 3478910 12 14 15 18 1920 已知已知N=12N=12個事件的發(fā)生時刻和結(jié)束時刻（見下表，其個事件的發(fā)生時刻和結(jié)束時刻（

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

14、更長一些 如何選擇事件，可以保證得到最長的事件序列呢？ 用用beginibegini表示事件表示事件i i的發(fā)生時刻，用的發(fā)生時刻，用endiendi表示事件表示事件i i的的結(jié)束時刻。結(jié)束時刻。 如果兩個事件如果兩個事件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 本題目的貪心策略：即為了得到當前情況下最優(yōu)的一本題目的貪心策略：即為了得到當前情況下最優(yōu)的一個結(jié)果，可以在當前可選的事件中選取編號最小的那個結(jié)果，可以在當前可選的事件中選取編號最小的那個進入序列，也就是選取最早結(jié)束的那個事件進入序個進入序列，也就是選取最早結(jié)束的那個事件進入序列。即：列。即： 第一個要選取的事件是最早結(jié)束的事件；第一個要選取的事件是最早結(jié)束的事件； 下一個要選取的事件，必須是上一個選取的事件結(jié)束

16、下一個要選取的事件，必須是上一個選取的事件結(jié)束之后開始的事件中最早結(jié)束的事件；之后開始的事件中最早結(jié)束的事件； 在程序中設(shè)置一個在程序中設(shè)置一個selectiselecti標記數(shù)組，表示事件標記數(shù)組，表示事件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】 區(qū)間覆蓋問題區(qū)間覆蓋問題【例例12.312.3】 區(qū)間覆蓋問題區(qū)間覆蓋問題例如例如M=5M=5

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

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

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

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

23、線段長度減少了原來一條線段長度減少了position1position1和和position0+1position0+1之間的距離，即：之間的距離，即： position1-position0-1 position1-position0-1。題目要求最小線段總長，可以找間隔最大的兩個相鄰區(qū)間，在它題目要求最小線段總長，可以找間隔最大的兩個相鄰區(qū)間，在它們之間斷開就可以了。這一過程相當于找們之間斷開就可以了。這一過程相當于找 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的方案下，將某條的方案下，將某條線段斷成兩截，并作可能的端點調(diào)整。線段斷成兩截，并作可能的端點調(diào)整。顯然，為了得到當前情況下最小的總長度，顯然，為了得到當前情況下最小的總長度，同樣應(yīng)該在間隔最大的兩個相鄰區(qū)間之間斷同樣應(yīng)該在間隔最大的兩個相鄰區(qū)間之間斷開。開。如果原來的方案是如果原來的方案是N=2N=2時總長最小的方案，時總長最小的方案，這一操作可以得到這一操作可以得到N=3N=3時總長最小

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

26、id sort1(int value,int n) / 排序函數(shù)（非遞增）排序函數(shù)（非遞增） 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是要覆蓋的區(qū)

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

28、=0;im;i+)for(i=0;im;i+)scanf(%d,&positioni); / scanf(%d,&positioni); / 輸入輸入mm個區(qū)間個區(qū)間sort1(position,m); / msort1(position,m); / m個區(qū)間降序排列個區(qū)間降序排列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; / 當前情況下所用線段總數(shù)當前情況下所用線段

29、總數(shù)int totallength=position0-positionm-1+1;int totallength=position0-positionm-1+1; / / 當前情況下所用線段總長當前情況下所用線段總長int devide=0; / int devide=0; / 當前最大的未斷開的區(qū)間距離當前最大的未斷開的區(qū)間距離while(nlinen)& / while(nline0) / (distancedevide0) / 還有不相鄰的區(qū)間還有不相鄰的區(qū)間 nline+; / nline+; / 再用一條線段再用一條線段totallength-=distancedevide; / totallength-=distancedevide; / 總長減少總長減少devide+; / devide+; / 覆蓋該區(qū)間的線段斷開，指向下一最大間隔覆蓋該區(qū)間的線段斷開，指向下一最大間隔 printf(printf(最小線段總長為：最小線段總長為：%dn,totallength);%dn,totallength);return 0;return 0; 118431n=1