第6章貪心算法

1、第六章第六章 貪心算法貪心算法 若在求解一個問題時，能根據(jù)每次所得到的局部最優(yōu)解，推導(dǎo)出全局最若在求解一個問題時，能根據(jù)每次所得到的局部最優(yōu)解，推導(dǎo)出全局最優(yōu)或最優(yōu)目標(biāo)。那么，我們可以根據(jù)這個策略，每次得到局部最優(yōu)解答，逐優(yōu)或最優(yōu)目標(biāo)。那么，我們可以根據(jù)這個策略，每次得到局部最優(yōu)解答，逐步而推導(dǎo)出問題，這種策略稱為步而推導(dǎo)出問題，這種策略稱為貪心法貪心法。下面我們看一些簡單例題。下面我們看一些簡單例題?！纠纠?】在在N行行M列的正整數(shù)矩陣中，要求從每行中選出列的正整數(shù)矩陣中，要求從每行中選出1個數(shù)，使得選出的總共個數(shù)，使得選出的總共N個個數(shù)的和最大。數(shù)的和最大?！舅惴ǚ治觥俊舅惴ǚ治觥?要使

2、總和最大，則每個數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個數(shù)。因此，要使總和最大，則每個數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個數(shù)。因此，我們設(shè)計出如下算法我們設(shè)計出如下算法:讀入讀入N, M,矩陣數(shù)據(jù)；矩陣數(shù)據(jù)；Total = 0;for (int I = 1; I =0) /將第i種商品全部裝入卡車 else 將(m+wi) 重量的物品i裝入卡車; i=i+1; /選擇下一種商品while (m0&inr; memset(s,0,sizeof(s); /初始化 j=0; minx=0; for (i=1;i=n;+i) /用貪心法求解 j+; if (j=r+1) j=1; /前前r個人為一

3、組，第個人為一組，第r+1個人回到第一個水龍個人回到第一個水龍 sj+=ai; /加上等待時間加上等待時間 minx+=sj; cout從取3張牌放到 （9 11 10 10）- 從取1張牌放到（10 10 10 10）?！据斎敫袷健?N（N 堆紙牌，1 = N = 100） A1 A2 An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai n;ave=0;step=0; for (i=1;iai; ave+=ai; /讀入各堆牌張數(shù)，求總張數(shù)讀入各堆牌張數(shù)，求總張數(shù)ave ave/=n; /求牌的平均張數(shù)求牌的平均張數(shù)avefor (i=1;i=n;+i) ai-=ave; /每堆牌的張數(shù)減去平均

4、數(shù)每堆牌的張數(shù)減去平均數(shù)i=1;j=n;while (ai=0&i1) -j; /過濾右邊的過濾右邊的0while (ij) ai+1+=ai; /將第將第i堆牌移到第堆牌移到第i+1堆中去堆中去ai=0; /第第i堆牌移走后變?yōu)槎雅埔谱吆笞優(yōu)?+step; /移牌步數(shù)計數(shù)移牌步數(shù)計數(shù) +i; /對下一堆牌進(jìn)行循環(huán)操作對下一堆牌進(jìn)行循環(huán)操作while (ai=0&ij) +i; /過濾移牌過程中產(chǎn)生的過濾移牌過程中產(chǎn)生的0 coutstependl; 點(diǎn)評：基本題，本題有點(diǎn)評：基本題，本題有3點(diǎn)比較關(guān)鍵：一是善于將每堆牌數(shù)減去平均數(shù)，簡化了點(diǎn)比較關(guān)鍵：一是善于將每堆牌數(shù)減去平均數(shù)，簡化了問題；

5、二是要過濾掉問題；二是要過濾掉0（不是所有的（不是所有的0，如，如-2，3，0，-1中的中的0是不能過濾的）；三是是不能過濾的）；三是負(fù)數(shù)張牌也可以移動，這是關(guān)鍵中的關(guān)鍵。負(fù)數(shù)張牌也可以移動，這是關(guān)鍵中的關(guān)鍵?！纠纠?】刪數(shù)問題（】刪數(shù)問題（NOI94）輸入一個高精度的正整數(shù)N，去掉其中任意S個數(shù)字后剩下的數(shù)字按原左右次序組成一個新的正整數(shù)。編程對給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。 輸出新的正整數(shù)。（N不超過240位）輸入數(shù)據(jù)均不需判錯?！据斎搿?n s【輸出】 最后剩下的最小數(shù)?！緲永斎搿?175438 4【樣例輸出】 13【算法分析】 由于正整數(shù)n的有效數(shù)位為24

6、0位，所以很自然地采用字符串類型存貯n。那么如何決定哪s位被刪除呢？是不是最大的s個數(shù)字呢？顯然不是，大家很容易舉出一些反例。為了盡可能逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字；否則刪除第一個遞減區(qū)間的首字符，這樣刪一位便形成了一個新數(shù)字串。然后回到串首，按上述規(guī)則再刪下一個數(shù)字。重復(fù)以上過程s次為止，剩下的數(shù)字串便是問題的解了。例如：n=175438 s=4 刪數(shù)的過程如下： n=175438 /刪掉7 15438 /刪掉5 1438 /刪掉4 138 /刪掉8 13 /解為13 這樣，刪數(shù)問題就

7、與如何尋找遞減區(qū)間首字符這樣一個簡單的問題對應(yīng)起來。不過還要注意一個細(xì)節(jié)性的問題，就是可能會出現(xiàn)字符串串首有若干0的情況，甚至整個字符串都是0的情況。按以上貪心策略編制的程序框架如下 輸入n，s； for (i=1;i=s;+i) /一共要刪除s個字符 for ( j=0;jnj+1 ) /找到第一個符合條件的 for ( k=j;k導(dǎo)彈導(dǎo)彈i的高度的高度；lp導(dǎo)彈導(dǎo)彈i的高度的高度)（ijk）。這樣可使得）。這樣可使得一套系統(tǒng)攔截的導(dǎo)彈數(shù)盡可能增多。一套系統(tǒng)攔截的導(dǎo)彈數(shù)盡可能增多。依次類推，直至分析了依次類推，直至分析了n枚導(dǎo)彈的高度為止。此時得出的枚導(dǎo)彈的高度為止。此時得出的k便為應(yīng)配備的

8、最少系統(tǒng)數(shù)。便為應(yīng)配備的最少系統(tǒng)數(shù)。參考程序主要框架如下：參考程序主要框架如下：k=1;lk=導(dǎo)彈導(dǎo)彈1的高度的高度; for (i=2;i=n;+i) p=0;for (j=1;j=導(dǎo)彈導(dǎo)彈i的高度的高度) if (p=0) p=j; else if (ljlp) p=j; /貪心貪心 if (p=0) +k;lk=導(dǎo)彈導(dǎo)彈i的高度的高度; /增加一套新系統(tǒng)增加一套新系統(tǒng) else lp=導(dǎo)彈導(dǎo)彈i的高度的高度; /貪心貪心,更新第更新第p套系統(tǒng)的最低高度套系統(tǒng)的最低高度 輸出應(yīng)配備的最少系統(tǒng)數(shù)輸出應(yīng)配備的最少系統(tǒng)數(shù)K。 【例7】活動選擇 學(xué)校在最近幾天有n個活動，這些活動都需要使用學(xué)校的大

9、禮堂，在同一時間，禮堂只能被一個活動使。由于有些活動時間上有沖突，學(xué)校辦公室人員只好讓一些活動放棄使用禮堂而使用其他教室。 現(xiàn)在給出n個活動使用禮堂的起始時間begini和結(jié)束時間endi(begini endi)，請你幫助辦公室人員安排一些活動來使用禮堂，要求安排的活動盡量多。 【輸入】 第一行一個整數(shù)n(n=1000)； 接下來的n行，每行兩個整數(shù)，第一個begini，第二個是endi(begini endi =32767)【輸出】 輸出最多能安排的活動個數(shù)?！緲永斎搿?13 51 412 148 120 68 116 105 73 85 92 13【樣例輸出】 4 【算法分析】 算法模

10、型：給n個開區(qū)間（begini,endi）, 選擇盡量多的區(qū)間, 使得兩兩不交。 做法: 首先按照end1=end2=endn的順序排序,依次考慮各個活動, 如果沒有和已經(jīng)選擇的活動沖突, 就選; 否則就不選。 正確性: 如果不選end1, 假設(shè)第一個選擇的是endi,則如果endi和end1不交叉則多選一個end1更劃算; 如果交叉則把endi換成end1不影響后續(xù)選擇。 【參考程序】#includeusing namespace std;int n,begin1001,end1001;void init() cinn; for(int i=1;ibeginiendi;void qsort(

11、int x,int y) int i,j,mid,t; i=x;j=y;mid=end(x+y)/2; while(i=j) while(endimid) -j; if(i=j) t=endj;endj=endi;endi=t; t=beginj;beginj=begini;begini=t; +i;j; if(xj) qsort(x,j); if(iy) qsort(i,y); void solve() int ans=0; for(int i=1,t=-1;i=t) +ans;t=endi;/如果當(dāng)前活動與之前最后結(jié)束的活動不沖突， 就接受當(dāng)前活動。 coutansendl;int mai

12、n() init(); qsort(1,n); solve(); return 0; 【例8】整數(shù)區(qū)間 請編程完成以下任務(wù)： 1.從文件中讀取閉區(qū)間的個數(shù)及它們的描述； 2.找到一個含元素個數(shù)最少的集合,使得對于每一個區(qū)間,都至少有一個整數(shù)屬于該集合，輸出該集合的元素個數(shù)。 【輸入】 首行包括區(qū)間的數(shù)目n,1=n=10000,接下來的n行,每行包括兩個整數(shù)a,b,被一空格隔開,0=a=b=10000,它們是某一個區(qū)間的開始值和結(jié)束值?！据敵觥?第一行集合元素的個數(shù),對于每一個區(qū)間都至少有一個整數(shù)屬于該區(qū)間,且集合所包含元素數(shù)目最少。【樣例輸入】 43 62 40 24 7【樣例輸出】2 【算法

13、分析】 算法模型：給n個閉區(qū)間ai,bi, 在數(shù)軸上選盡量少的點(diǎn),使每個區(qū)間內(nèi)至少有一個點(diǎn)。 算法：首先按b1=b2=.=bn排序。每次標(biāo)記當(dāng)前區(qū)間的右端點(diǎn)x，并右移當(dāng)前區(qū)間指針，直到當(dāng)前區(qū)間不包含x,再重復(fù)上述操作。 如下圖，如果選灰色點(diǎn)，移動到黑色點(diǎn)更優(yōu)。 【參考程序】#includeusing namespace std;int a10001,b10001,sum=0,n,m;void qsort(int x,int y) /多關(guān)鍵字快排 int i,j,mid1,mid2,t; i=x;j=y;mid1=b(x+y)/2;mid2=a(x+y)/2; while(i=j) while(

14、bimid1|(bi=mid1)&(aimid1|(bj=mid1)&(ajmid2) -j; if(i=j) t=bj;bj=bi;bi=t; t=aj;aj=ai;ai=t; +i; -j; if(xj) qsort(x,j); if(in; for(int i=1;iaibi; qsort(1,n); for(int i=1,x=-1;i=ai) continue; /如果當(dāng)前區(qū)間包含標(biāo)記點(diǎn)，就跳過。 +sum; x=bi; /更新標(biāo)記點(diǎn)。 coutsum從取3張牌放到 （9 11 10 10）- 從取1張牌放到（10 10 10 10）?！据斎敫袷健俊据斎敫袷健縉（N 堆紙牌，1 =

15、N = 100）A1 A2 An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）【輸出格式】【輸出格式】所有堆均達(dá)到相等時的最少移動次數(shù)?！緲永斎搿俊緲永斎搿?Playcard.in)49 8 17 6 【樣例輸出【樣例輸出】(Playcard.out)33、攔截導(dǎo)彈問題（、攔截導(dǎo)彈問題（NOIP1999）【問題描述】【問題描述】某國為了防御敵國的導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)，但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。所以一套系統(tǒng)有可能不能攔截所有的導(dǎo)彈。

16、輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度不大于30000的正整數(shù)）。計算要攔截所有導(dǎo)彈最小需要配備多少套這種導(dǎo)彈攔截系統(tǒng)。【輸入格式】【輸入格式】 n顆依次飛來的高度（1n1000）.【輸出格式】【輸出格式】 要攔截所有導(dǎo)彈最小配備的系統(tǒng)數(shù)k?！据斎霕永俊据斎霕永縨issile.in 389 207 155 300 299 170 158 65【輸出樣例】【輸出樣例】missile.out 24、排隊接水、排隊接水(water.pas)【問題描述】【問題描述】 有n個人在一個水龍頭前排隊接水，假如每個人接水的時間為Ti，請編程找出這n個人排隊的一種順序，使得n個人的平均等待時間最小?！据斎敫?/p>

17、式】【輸入格式】 輸入文件共兩行，第一行為n；第二行分別表示第1個人到第n個人每人的接水時間T1，T2，Tn，每個數(shù)據(jù)之間有1個空格?！据敵龈袷健俊据敵龈袷健?輸出文件有兩行，第一行為一種排隊順序，即1到n的一種排列；第二行為這種排列方案下的平均等待時間(輸出結(jié)果精確到小數(shù)點(diǎn)后兩位)。【輸入輸出樣例】【輸入輸出樣例】water.in103 2 7 8 1 4 9 6 10 556 12 1 99 1000 234 33 55 99 812water.out532.005、最大整數(shù)（、最大整數(shù)（Noip1998連接多位數(shù)）連接多位數(shù)）【問題描述】【問題描述】 設(shè)有n個正整數(shù)（n20），將它們聯(lián)接

18、成一排，組成一個最大的多位整數(shù)。 例如：n=3時，3個整數(shù)13，312，343聯(lián)接成的最大整數(shù)為：34331213 又如：n=4時，4個整數(shù)7，13，4，246聯(lián)接成的最大整數(shù)為：7424613【輸入格式】【輸入格式】n n個數(shù)【輸出格式】【輸出格式】聯(lián)接成的多位數(shù)【輸入樣例】【輸入樣例】maxnum.in313 312 343【輸出樣例】【輸出樣例】maxnum.out 343312136、紀(jì)念品分組、紀(jì)念品分組(NOIP2007)【題目描述】【題目描述】 元旦快到了，校學(xué)生會讓樂樂負(fù)責(zé)新年晚會的紀(jì)念品發(fā)放工作。為使得參加晚會的同學(xué)所獲得的紀(jì)念品價值相對均衡，他要把購來的紀(jì)念品根據(jù)價格進(jìn)行分

19、組，但每組最多只能包括兩件紀(jì)念品，并且每組紀(jì)念品的價格之和不能超過一個給定的整數(shù)。為了保證在盡量短的時間內(nèi)發(fā)完所有紀(jì)念品，樂樂希望分組的數(shù)目最少。 你的任務(wù)是寫一個程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目?！据斎敫袷健俊据斎敫袷健?輸入文件group.in包含n+2行： 第1行包括一個整數(shù)w，為每組紀(jì)念品價格之和的上限。 第2行為一個整數(shù)n，表示購來的紀(jì)念品的總件數(shù)。 第3n+2行每行包含一個正整數(shù)pi (5 = pi = w)，表示所對應(yīng)紀(jì)念品的價格?！据敵龈袷健俊据敵龈袷健?輸出文件group.out僅一行，包含一個整數(shù)，即最少的分組數(shù)目。【輸入輸出樣例】【輸入輸出樣例

20、】【限制】【限制】 50%的數(shù)據(jù)滿足：1 = n = 15 100%的數(shù)據(jù)滿足：1 = n = 30000, 80 = w = 200group.ingroup.in1009902020305060708090group.outgroup.out67、合并果子、合并果子(Noip2004)【問題描述】【問題描述】 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次

21、合并所耗體力之和。 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個最小的體力耗費(fèi)值。 例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?1、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為 12。所以多多總共耗費(fèi)體力=3+12=15。可以證明15為最小的體力耗費(fèi)值?！据斎胛募俊据斎胛募?輸入文件fruit.in包括兩行，第一行是一個整數(shù)n（1 = n = 10000），表示果子的種類

22、數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai（1 = ai = 20000）是第i種果子的數(shù)目。【輸出文件】【輸出文件】 輸出文件fruit.out包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個值小于231?！緲永斎搿俊緲永斎搿?1 2 9【樣例輸出】【樣例輸出】15【數(shù)據(jù)規(guī)模】【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，保證有n = 1000；對于50%的數(shù)據(jù)，保證有n = 5000；對于全部的數(shù)據(jù)，保證有n = 10000。8、美元匯率（、美元匯率（DOLLARS.PAS）【問題描述】【問題描述】 在以后的若干天里戴維將學(xué)習(xí)美元與德國馬克的匯率。編寫程序幫助戴維何時應(yīng)買或賣馬克或美元，使他從100美元開始，最后能獲得最高可能的價值?！据斎敫袷健俊据斎敫袷健?輸入文件的第一行是一個自然數(shù)N，1N100，表示戴維學(xué)習(xí)匯率的天數(shù)。接下來的N行中每行是一個自然數(shù)A，1A1