第6章-貪心算法

第六章貪心算法一、基本概念所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關。所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性。二、基本思路

1.建立數(shù)學模型來描述問題。

2.把求解的問題分成若干個子問題。

3.對每一子問題求解，得到子問題的局部最優(yōu)解。

4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。三、適用問題貪心策略適用的前提是：局部最優(yōu)策略能導致產(chǎn)生全局最優(yōu)解。四、實現(xiàn)框架從問題的某一初始解出發(fā)；

while（能朝給定總目標前進一步）

{

利用可行的決策，求出可行解的一個解元素；

}

由所有解元素組合成問題的一個可行解；五、貪心策略的選擇因為用貪心算法只能通過解局部最優(yōu)解的策略來達到全局最優(yōu)解，因此，一定要注意判斷問題是否適合采用貪心算法策略，找到的解是否一定是問題的最優(yōu)解?！纠?】排隊打水問題有N個人排隊到R個水龍頭去打水，他們裝滿水桶的時間為T1，T2，…，Tn為整數(shù)且各不相等，應如何安排他們的打水順序才能使他們花費的時間最少？【算法分析】由于排隊時，越靠前面的計算的次數(shù)越多，顯然越小的排在越前面得出的結果越?。梢杂脭?shù)學方法簡單證明，就不再贅述），所以這道題可以用貪心法解答，基本步驟：(1)將輸入的時間按從小到大排序；(2)將排序后的時間按順序依次放入每個水龍頭的隊列中；(3)統(tǒng)計，輸出答案。【樣例輸入】42//4人打水，2個水龍頭2645//每個打水時間參考程序主要框架如下：cin>>n>>r;memset(s,0,sizeof(s));//初始化j=0;minx=0;for(i=1;i<=n;++i)//用貪心法求解{j++;if(j==r+1)j=1;//前r個人為一組，第r+1個人回到第1個水龍s[j]+=a[i];//加上等待時間minx+=s[j];}cout<<minx;//輸出解答【樣例輸出】23//總共花費時間【例2】均分紙牌（NOIP2002）

有N堆紙牌，編號分別為1，2，…,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移動。

移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如N=4，4堆紙牌數(shù)分別為：①9②8③17④6

移動3次可達到目的：

從③取4張牌放到④（981310）->從③取3張牌放到②（9111010）->從②取1張牌放到①（10101010）?！据斎敫袷健?/p>

N（N堆紙牌，1<=N<=100）

A1A2…An（N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000）【輸出格式】

所有堆均達到相等時的最少移動次數(shù)?！緲永斎搿縋laycard.in

4

98176【樣例輸出】Playcard.out

3【算法分析】如果你想到把每堆牌的張數(shù)減去平均張數(shù)，題目就變成移動正數(shù)，加到負數(shù)中，使大家都變成0，那就意味著成功了一半！拿例題來說，平均張數(shù)為10,原張數(shù)9，8，17，6，變?yōu)?1，-2，7，-4，其中沒有為0的數(shù)，我們從左邊出發(fā)：要使第1堆的牌數(shù)-1變?yōu)?，只須將-1張牌移到它的右邊（第2堆）-2中；結果是-1變?yōu)?，-2變?yōu)?3，各堆牌張數(shù)變?yōu)?，-3，7，-4；同理：要使第2堆變?yōu)?，只需將-3移到它的右邊（第3堆）中去，各堆牌張數(shù)變?yōu)?，0，4，-4；要使第3堆變?yōu)?，只需將第3堆中的4移到它的右邊（第4堆）中去，結果為0，0，0，0，完成任務。每移動1次牌，步數(shù)加1。也許你要問，負數(shù)張牌怎么移，不違反題意嗎？其實從第i堆移動-m張牌到第i+1堆，等價于從第i+1堆移動m張牌到第i堆，步數(shù)是一樣的。如果張數(shù)中本來就有為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，現(xiàn)在第3堆已經(jīng)變?yōu)?了，可節(jié)省1步，余下繼續(xù)。參考程序主要框架如下：cin>>n;ave=0;step=0;for(i=1;i<=n;++i){cin>>a[i];ave+=a[i];//讀入各堆牌張數(shù)，求總張數(shù)ave}ave/=n;//求牌的平均張數(shù)avefor(i=1;i<=n;++i)a[i]-=ave;//每堆牌的張數(shù)減去平均數(shù)i=1;j=n;while(a[i]==0&&i<n)++i;//過濾左邊的0while(a[j]==0&&j>1)--j;//過濾右邊的0while(i<j){a[i+1]+=a[i];//將第i堆牌移到第i+1堆中去a[i]=0;//第i堆牌移走后變?yōu)?++step;//移牌步數(shù)計數(shù)++i;//對下一堆牌進行循環(huán)操作while(a[i]==0&&i<j)++i;//過濾移牌過程中產(chǎn)生的0}cout<<step<<endl;點評：基本題，本題有3點比較關鍵：一是善于將每堆牌數(shù)減去平均數(shù)，簡化了問題；二是要過濾掉0（不是所有的0，如-2，3，0，-1中的0是不能過濾的）；三是負數(shù)張牌也可以移動，這是關鍵中的關鍵?！纠?】刪數(shù)問題（NOI94）輸入一個高精度的正整數(shù)N，去掉其中任意S個數(shù)字后剩下的數(shù)字按原左右次序組成一個新的正整數(shù)。編程對給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。

輸出新的正整數(shù)。（N不超過240位）輸入數(shù)據(jù)均不需判錯。【輸入】ns【輸出】

最后剩下的最小數(shù)?！緲永斎搿?754384【樣例輸出】13【算法分析】

由于正整數(shù)n的有效數(shù)位為240位，所以很自然地采用字符串類型存貯n。那么如何決定哪s位被刪除呢？是不是最大的s個數(shù)字呢？顯然不是，大家很容易舉出一些反例。為了盡可能逼近目標，我們選取的貪心策略為：每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字；否則刪除第一個遞減區(qū)間的首字符，這樣刪一位便形成了一個新數(shù)字串。然后回到串首，按上述規(guī)則再刪下一個數(shù)字。重復以上過程s次為止，剩下的數(shù)字串便是問題的解了。例如：n=175438s=4刪數(shù)的過程如下：n=175438//刪掉715438//刪掉51438//刪掉4138//刪掉813//解為13這樣，刪數(shù)問題就與如何尋找遞減區(qū)間首字符這樣一個簡單的問題對應起來。不過還要注意一個細節(jié)性的問題，就是可能會出現(xiàn)字符串串首有若干0的情況，甚至整個字符串都是0的情況。按以上貪心策略編制的程序框架如下輸入n，s；for(i=1;i<=s;++i){//一共要刪除s個字符for(j=0;j<len-1;++j)//從串首開始找，len是n的長度if(n[j]>n[j+1]){//找到第一個符合條件的for(k=j;k<len-1;++k)//刪除字符串n的第j個字符，后面字符往前整n[k]=n[k+1];break;}--len;//長度減1}輸出n；//刪去串首可能產(chǎn)生的無用零【參考程序】字符串string#include<string>#include<iostream>usingnamespacestd;intmain(){ ints; stringn; cin>>n>>s; for(inti;i=0,s--;n.erase(i,1)) while(i<n.size()&&n[i]<=n[i+1]) ++i; while(n.size()>1&&n[0]=='0') n.erase(0,1); cout<<n<<endl; return0;}【例4】攔截導彈問題（NOIP1999）

某國為了防御敵國的導彈襲擊，開發(fā)出一種導彈攔截系統(tǒng)，但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲，由于該系統(tǒng)還在試用階段。所以一套系統(tǒng)有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度不大于30000的正整數(shù)）。計算要攔截所有導彈最小需要配備多少套這種導彈攔截系統(tǒng)?！据斎敫袷健?/p>

n顆依次飛來的高度（1≤n≤1000）.【輸出格式】

要攔截所有導彈最小配備的系統(tǒng)數(shù)k。【輸入樣例】missile.in

38920715530029917015865【輸出樣例】missile.out

2【輸入輸出樣例】輸入：導彈高度：79685輸出：導彈攔截系統(tǒng)K=2輸入：導彈高度：432輸出：導彈攔截系統(tǒng)K=1【算法分析】按照題意，被一套系統(tǒng)攔截的所有導彈中，最后一枚導彈的高度最低。設：k為當前配備的系統(tǒng)數(shù)；l[k]為被第k套系統(tǒng)攔截的最后一枚導彈的高度，簡稱系統(tǒng)k的最低高度（1≤k≤n）。我們首先設導彈1被系統(tǒng)1所攔截（k←1,l[k]←導彈1的高度）。然后依次分析導彈2，…，導彈n的高度。若導彈i的高度高于所有系統(tǒng)的最低高度，則斷定導彈i不能被這些系統(tǒng)所攔截，應增設一套系統(tǒng)來攔截導彈I(k←k+1,l[k]←導彈i的高度)；若導彈i低于某些系統(tǒng)的最低高度，那么導彈i均可被這些系統(tǒng)所攔截。究竟選擇哪個系統(tǒng)攔截可使得配備的系統(tǒng)數(shù)最少，我們不妨采用貪心策略，選擇其中最低高度最小（即導彈i的高度與系統(tǒng)最低高度最接近）的一套系統(tǒng)p(l[p]=min{l[j]|l[j]>導彈i的高度}；l[p]←導彈i的高度)（1≤j≤k）。這樣可使得一套系統(tǒng)攔截的導彈數(shù)盡可能增多。依次類推，直至分析了n枚導彈的高度為止。此時得出的k便為應配備的最少系統(tǒng)數(shù)。參考程序主要框架如下：k=1;l[k]=導彈1的高度;for(i=2;i<=n;++i){

p=0;for(j=1;j<=k;++j)if(l[j]>=導彈i的高度){if(p==0)p=j;

elseif(l[j]<l[p])p=j;}//貪心

if(p==0){++k;l[k]=導彈i的高度;}//增加一套新系統(tǒng)

elsel[p]=導彈i的高度;//貪心,更新第p套系統(tǒng)的最低高度

}輸出應配備的最少系統(tǒng)數(shù)K。

【例5】活動選擇學校在最近幾天有n個活動，這些活動都需要使用學校的大禮堂，在同一時間，禮堂只能被一個活動使。由于有些活動時間上有沖突，學校辦公室人員只好讓一些活動放棄使用禮堂而使用其他教室?，F(xiàn)在給出n個活動使用禮堂的起始時間begini和結束時間endi(begini<endi)，請你幫助辦公室人員安排一些活動來使用禮堂，要求安排的活動盡量多?！据斎搿康谝恍幸粋€整數(shù)n(n<=1000)；接下來的n行，每行兩個整數(shù)，第一個begini，第二個是endi(begini<endi<=32767)【輸出】輸出最多能安排的活動個數(shù)?！緲永斎搿?13514121481206811610573859213【樣例輸出】4

【算法分析】

?算法模型：給n個開區(qū)間（begini,endi）,選擇盡量多的區(qū)間,使得兩兩不交。

?做法:首先按照end1<=end2<…<=endn的順序排序,依次考慮各個活動,如果沒有和已經(jīng)選擇的活動沖突,就選;否則就不選。

?正確性:如果不選end1,假設第一個選擇的是endi,則如果endi和end1不交叉則多選一個end1更劃算;如果交叉則把endi換成end1不影響后續(xù)選擇。

【參考程序】#include<iostream>usingnamespacestd;intn,begin[1001],end[1001];voidinit(){cin>>n;for(inti=1;i<=n;i++)cin>>begin[i]>>end[i];}voidqsort(intx,inty){inti,j,mid,t;i=x;j=y;mid=end[(x+y)/2];while(i<=j){while(end[i]<mid)++i;while(end[j]>mid)--j;if(i<=j){t=end[j];end[j]=end[i];end[i]=t;t=begin[j];begin[j]=begin[i];begin[i]=t;++i;j;}}if(x<j)qsort(x,j);if(i<y)qsort(i,y);}

voidsolve(){intans=0;for(inti=1,t=-1;i<=n;++i)//在初始化循環(huán)變量的同時，初始化t。//令t=-1可以使第一個區(qū)間與其他區(qū)間的操作相同if(begin[i]>=t){//當前活動開始時間與之前選擇的活動結束時間不沖突，就接受當前活動++ans;t=end[i];}cout<<ans<<endl;}intmain(){init();qsort(1,n);solve();return0;}

【例6】整數(shù)區(qū)間

請編程完成以下任務：1.從文件中讀取閉區(qū)間的個數(shù)及它們的描述；2.找到一個含元素個數(shù)最少的集合,使得對于每一個區(qū)間,都至少有一個整數(shù)屬于該集合，輸出該集合的元素個數(shù)?！据斎搿渴仔邪▍^(qū)間的數(shù)目n,1<=n<=10000,接下來的n行,每行包括兩個整數(shù)a,b,被一空格隔開,0<=a<=b<=10000,它們是某一個區(qū)間的開始值和結束值?！据敵觥康谝恍屑显氐膫€數(shù),對于每一個區(qū)間都至少有一個整數(shù)屬于該區(qū)間,且集合所包含元素數(shù)目最少?！緲永斎搿?36240247【樣例輸出】2

【算法分析】?算法模型：給n個閉區(qū)間[ai,bi],在數(shù)軸上選盡量少的點,使每個區(qū)間內(nèi)至少有一個點。?算法：首先按b1<=b2<=...<=bn排序。每次標記當前區(qū)間的右端點x，并右移當前區(qū)間指針，直到當前區(qū)間不包含x,再重復上述操作。?如下圖，如果選灰色點，移動到黑色點更優(yōu)。

【參考程序】#include<iostream>usingnamespacestd;inta[10001],b[10001],sum=0,n,m;voidqsort(intx,inty)//多關鍵字快排{inti,j,mid1,mid2,t;i=x;j=y;mid1=b[(x+y)/2];mid2=a[(x+y)/2];while(i<=j){while(b[i]<mid1||((b[i]==mid1)&&(a[i]<mid2)))++i;while(b[j]>mid1||((b[j]==mid1)&&(a[j]>mid2)))--j;if(i<=j){t=b[j];b[j]=b[i];b[i]=t;t=a[j];a[j]=a[i];a[i]=t;++i;--j;}}if(x<j)qsort(x,j);if(i<y)qsort(i,y);}

intmain(){cin>>n;for(inti=1;i<=n;++i)cin>>a[i]>>b[i];qsort(1,n);for(inti=1,x=-1;i<=n;++i)//在初始化循環(huán)變量的同時，初始化x。//令x=-1可以使第一個區(qū)間與其他區(qū)間的操作相同。{if(x>=a[i])continue;//如果當前區(qū)間包含標記點，就跳過。++sum;x=b[i];//更新標記點。}cout<<sum<<endl;return0;}【上機練習】1、刪數(shù)問題（NOI94）【問題描述】輸入一個高精度的正整數(shù)n(≤240位)，去掉其中任意s個數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。【輸入格式】ns【輸出格式】

最后剩下的最小數(shù)?！据斎霕永縟elete.in1754384【輸出樣例】delete.out132、均分紙牌（NOIP2002）【問題描述】

有N堆紙牌，編號分別為1，2，…,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若干張紙牌，然后移動。

移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。

例如N=4，4堆紙牌數(shù)分別為：①9②8③17④6

移動3次可達到目的：

從③取4張牌放到④（981310）->從③取3張牌放到②（9111010）->從②取1張牌放到①（10101010）。【輸入格式】N（N堆紙牌，1<=N<=100）A1A2…An（N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000）【輸出格式】所有堆均達到相等時的最少移動次數(shù)。【樣例輸入】(Playcard.in)

4

98176【樣例輸出】(Playcard.out)

33、攔截導彈問題（NOIP1999）【問題描述】某國為了防御敵國的導彈襲擊，開發(fā)出一種導彈攔截系統(tǒng)，但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲，由于該系統(tǒng)還在試用階段。所以一套系統(tǒng)有可能不能攔截所有的導彈。輸入導彈依次飛來的高度（雷達給出的高度不大于30000的正整數(shù)）。計算要攔截所有導彈最小需要配備多少套這種導彈攔截系統(tǒng)?！据斎敫袷健縩顆依次飛來的高度（1≤n≤1000）.【輸出格式】

要攔截所有導彈最小配備的系統(tǒng)數(shù)k?！据斎霕永縨issile.in38920715530029917015865【輸出樣例】missile.out24、排隊接水(water.pas)【問題描述】

有n個人在一個水龍頭前排隊接水，假如每個人接水的時間為Ti，請編程找出這n個人排隊的一種順序，使得n個人的平均等待時間最小?！据斎敫袷健?/p>

輸入文件共兩行，第一行為n；第二行分別表示第1個人到第n個人每人的接水時間T1，T2，…，Tn，每個數(shù)據(jù)之間有1個空格。【輸出格式】

輸出文件有兩行，第一行為一種排隊順序，即1到n的一種排列；第二行為這種排列方案下的平均等待時間(輸出結果精確到小數(shù)點后兩位)?！据斎胼敵鰳永?water.in 10 32781496105 56121991000234335599812 water.out532.005、最大整數(shù)（Noip1998連接多位數(shù)）【問題描述】

設有n個正整數(shù)（n≤20），將它們聯(lián)接成一排，組成一個最大的多位整數(shù)。

例如：n=3時，3個整數(shù)13，312，343聯(lián)接成的最大整數(shù)為：34331213

又如：n=4時，4個整數(shù)7，13，4，246聯(lián)接成的最大整數(shù)為：7424613【輸入格式】nn個數(shù)【輸出格式】聯(lián)接成的多位數(shù)【輸入樣例】maxnum.in313312343【輸出樣例】maxnum.out343312136、紀念品分組(NOIP2007)【題目描述】

元旦快到了，校學生會讓樂樂負責新年晚會的紀念品發(fā)放工作。為使得參加晚會的同學所獲得的紀念品價值相對均衡，他要把購來的紀念品根據(jù)價格進行分組，但每組最多只能包括兩件紀念品，并且每組紀念品的價格之和不能超過一個給定的整數(shù)。為了保證在盡量短的時間內(nèi)發(fā)完所有紀念品，樂樂希望分組的數(shù)目最少。

你的任務是寫一個程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目?！据斎敫袷健?/p>

輸入文件group.in包含n+2行：

第1行包括一個整數(shù)w，為每組紀念品價格之和的上限。

第2行為一個整數(shù)n，表示購來的紀念品的總件數(shù)。

第3~n+2行每行包含一個正整數(shù)pi(5<=pi<=w)，表示所對應紀念品的價格?！据敵龈袷健?/p>

輸出文件group.out僅一行，包含一個整數(shù)，即最少的分組數(shù)目?！据斎胼敵鰳永俊鞠拗啤?0%的數(shù)據(jù)滿足：1<=n<=15100%的數(shù)據(jù)滿足：1<=n<=30000,80<=w<=200group.in1009902020305060708090group.out67、合并果子(Noip2004)【問題描述】

在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。

每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。

因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。

例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?、2堆合并，新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費體力為12。所以多多總共耗費體力=3+12=15?？梢宰C明15為最小的體力耗費值。【輸入文件】

輸入文件fruit.in包括兩行，第一行是一個整數(shù)n（1<=n<=100