談貪心算法

談?wù)勜澬乃惴?/span>

例1.背包問題

【題目描述】

這是一大家很熟悉的背包問題。給定n種貨物和一個載重量為

m的背包。已知第i種貨物的重量為wi ,其總價值為pi，編程

確定一個裝貨方案，使得裝入背包中貨物的總價值最大。輸出

此總價值和裝貨方案。

【算法分析】

0，1背包問題對每種物品只有兩種選擇：選和不選，可用動

態(tài)規(guī)劃解決。而背包問題，可以選擇物品的一部分裝載，這樣就可

以把背包裝滿，用貪心算法可求得最優(yōu)解。采用貪心標(biāo)準(zhǔn)是：選擇

單位重量價值高的貨物優(yōu)先裝入，這樣才能保證背包中所裝貨物總

價值最大。而0，1背包用貪心算法卻不能得到整體最優(yōu)，為什么

呢？我們來看一個例子：

有一背包容

量為50千克，有三種貨物：

物品1重10千克；價值60元；

物品2重20千克，價值100元；

物品3重30千克；價值120元。

1

20

20

10

總價值：（用貪心算法）

80+100+60=240

對于0，1背包問題，貪心選擇之所以不能得到最

優(yōu)解是因為它無法保證最終將背包裝滿，部分背包的 閑置使單位

重量背包空間的價值降低。

例2．排隊問題

【題目描述】

在一個醫(yī)院B 超室，有n個人要做不同身體部位的B超，

已知每個人需要處理的時間為ti，（0）,請求出一種排列次序，

使每個人排隊等候時間總和最小。

輸入數(shù)據(jù)：第1行一個正整數(shù)n（你<=10000》，第2行有n

2

個不超過 1000的正整數(shù)ti.

輸出要求：n個人排隊時間最小總和。

輸入輸出樣例

輸入：4

5 10 8 7

輸出：

67

【算法分析】

本題貪心算法：n個人時間從小到大排序，就是這n個人最佳

排隊方案。求部分和的和即為所求。

反證法證明：假設(shè)有最優(yōu)解序列：s1,s2…sn,如s1不是最小

的Tmin，不妨設(shè)sk=Tmin,將s1與sk對調(diào)，顯然，對sk之后的

人無影響，對sk之前的人等待都減少了，(s1-sk)>0,從而新的序列

比原最優(yōu)序列好，這與假設(shè)矛盾，故s1為最小時間，同理可證

s2…sn依次最小。

例3．:數(shù)列極差問題

【題目描述】

在黑板上寫了N個正整數(shù)做成的一個數(shù)列，進行如下操作：

每一次擦去其中的兩個數(shù)a和b，然后在數(shù)列中加入一個數(shù)a×b+1，

如此下去直至黑板上剩下一個數(shù)，在所有按這種操作方式最后得到

3

的數(shù)中，最大的max，最小的為min，則該數(shù)列的極差定義為

M=max-min。

編程任務(wù)：對于給定的數(shù)列，編程計算出極差M。

輸入輸出樣例：

輸入：

4

2 1 4 3

輸出：

13

【算法分析】

當(dāng)看到此題時，我們會發(fā)現(xiàn)求max與求min是兩個相似的過

程。若我們把求解max與min的過程分開，著重探討求max的問

題。

下面我們以求max為例來討論此題用貪心策略求解的合理

性。

討論：假設(shè)經(jīng)（Ｎ－3）次變換后得到３個數(shù)：a ,b , max＇（max＇

≥ａ≥ｂ），其中max＇是（Ｎ－２）個數(shù)經(jīng)（Ｎ－３）次ｆ變換后

所得的最大值，此時有兩種求值方式，設(shè)其所求值分別為 z1，z2，

則有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ

+１所以z1－z2＝max＇－ｂ≥０若經(jīng)（Ｎ－２）次變換后所得的

３個數(shù)為：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不為（Ｎ－２）次變換

4

后的最大值，即ｍ＜max＇則此時所求得的最大值為：

z3＝（ａ×ｂ+１）×ｍ+１此時z1－z3＝(１+ａｂ）（max＇－

ｍ）＞０ 所以此時不為最優(yōu)解。

所以若使第ｋ（１≤ｋ≤Ｎ－１）次變換后所得值最大，必使

（ｋ－１）次變換后所得值最大（符合貪心策略的特點2），在進

行第ｋ次變換時，只需取在進行（ｋ－１）次變換后所得數(shù)列中的

兩最小數(shù)ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合貪心

策略特點1），因此此題可用貪心策略求解。在求ｍin時，我們只

需在每次變換的數(shù)列中找到兩個最大數(shù)ｐ，ｑ施加作用 ｆ：ｐ←

ｐ×ｑ+１，ｑ←-∞即可．原理同上。

這是一道兩次運用貪心策略解決的一道問題，它要求選手有較

高的數(shù)學(xué)推理能力。

例4．整數(shù)區(qū)間

【題目描述】

我們定義一個整數(shù)區(qū)間[a,b],a,b是一個從a開始至b 結(jié)束的

連續(xù)整數(shù)的集合。編一個程序，對給定的 n個區(qū)間，找出滿足下

述條件的所含元素個數(shù)最少的集合中元素的個數(shù)：對于所給定的每

一個區(qū)間，都至少有兩個不同的整數(shù)屬于該集合。(1<=n<=10000,

0<=a<=b<=1000)

輸入輸出格式：

輸入：第一行一個正整數(shù)n，接下來有n行，每行給定一個區(qū)

5

間的a,b值

輸出：一個正整數(shù)，即滿足條件的集合所包含的最少元素個數(shù)

輸入輸出樣例

輸入： 輸出：

4 4

3 6

2 4

0 2

4 7

【算法分析】

本題數(shù)據(jù)規(guī)模較大，用搜索做會超時，而動態(tài)規(guī)劃無從下手。

考慮貪心算法。題目意思是要找一個集合，該集合中的數(shù)的個數(shù)既

要少又要和所給定的所有區(qū)間有交集。（每個區(qū)間至少有兩個該集

合中的數(shù)）。我們可以從所給的區(qū)間中選數(shù)，為了選盡量少的數(shù)，

應(yīng)該使所選的數(shù)和更多的區(qū)間有交集這就是貪心的標(biāo)準(zhǔn)。一開始將

所有區(qū)間按照右端點從小到大排序。從第一個區(qū)間開始逐個向后檢

查，看所選出的數(shù)與所查看的區(qū)間有無交集，有兩個則跳過，只有

一個數(shù)相交，就從當(dāng)前區(qū)間中選出最大的一個數(shù)（即右端點），若

無交集，則從當(dāng)前區(qū)間選出兩個數(shù)，就（右端點，右端點-1），直

至最后一個區(qū)間。

#include //整數(shù)區(qū)間問題

using namespace std;

6

struct prince{

int left,right;//區(qū)間左右端點

}a[10000];

int n;

int result;//存放結(jié)果中的數(shù)

int cmp(const void *a,const void *b){

return (*(prince *)a).right-(*(prince *)b).right;

}

int work(){

qsort(a+1,n,sizeof(a[0]),cmp);//按區(qū)間右端點由小到大排序

int i,j,k;

int a1,a2;

a1=a[1].right-1;a2=a[1].right;result=2;

for(i=2;i<=n;i++)

{ if(a[i].left<=a1&& a[i].right>=a2)continue;//完全包含

if (a[i].left>a2 )//完全不包含

{a1=a[i].right-1;a2=a[i].right;result=result+2;}

if (a[i].left>a1 && a[i].right>a2 && a[i].left<=a2)

{a1=a2;a2=a[i].right;result++;}//只包含一個

}

return result;

}

7

int main(){

freopen("","r",stdin);

freopen("","w",stdout);

cin>>n;

int i;

for(i=1;i<=n;i++)

cin>>a[i].left>>a[i].right;

cout<

return 0;

}

例5．駱駝商隊Camel Trading

【題目描述】

在一片古老的大地上，雖然商業(yè)已經(jīng)非常繁榮，但是那里的人

們?nèi)匀谎永m(xù)著古老的交易方式。他們牽著駱駝在城市之間往來奔

波，販運成批的商品，換來一袋袋的金幣。

這片大陸上有N個城市，編號為1……N。在一些城市之間有

路可通，有路就有商隊。但是在不同的城市之間經(jīng)商所得的收益不

同，在下面的這個N=4的例子中，在城市1和城市2之間進行一

次交易可以獲得40枚金幣，在城市2和3之間交易一次可以獲得

50枚金幣，等等。

8

30

3

1

40 50 20

30

4

2

在任意兩個城市之間，這樣的交易只能進行一次。因為你第二

次販運你的商品時，人們對它們就不會感興趣了。

現(xiàn)在你只身來到這個大陸上，用有限的資金在每個城市中購買

了一支商隊。你需要想辦法讓你的這N支商隊給你帶來最大的經(jīng)

濟收益。

任務(wù)說明

給出這個大陸的地圖和每兩個城市之間的貿(mào)易值（如果這兩個

城市之間有路可通的話），你需要指揮你的N支商隊進行一次經(jīng)商，

使得這N支商隊在這次經(jīng)商中獲得的總收益最大。注意：你的每

支商隊只能進行一次交易，即它們只能從它們所在的城市到達(dá)一個

相鄰的城市。當(dāng)然，它們也可以不進行任何交易。

輸入數(shù)據(jù)

輸入文件的第一行有兩個整數(shù)N（1 ? N ? 100）、M（M ? 0），

分別表示這個大陸上的城市數(shù)和道路數(shù)。

接下來有M行，每行包括三個整數(shù)i、j（1 ? i,j ? N且i ? j）、

v(1 ? V ? 10000)，表示一條道路的信息。其中i和j表示這條路在

城市i和城市j之間，v表示沿著這條路進行一次交易所得的收益。

i和j的順序是無關(guān)的，并且任意兩個城市之間最多存在一條路。

9

輸出數(shù)據(jù)

你的輸出文件應(yīng)該2行，第1行包含N個整數(shù)。其中第k個

整數(shù)表示你在城市k中的商隊將要前往哪個城市進行交易（如果這

支商隊進行交易的話）或者為0（如果這支商隊不進行任何交易）。

第2行輸出最大收益值。

輸入輸出樣例

樣例圖示

4 5 2 3 1 2

1 2 40 150

1 3 30

2 3 50

2 4 30

3 4 20 最大收益=40+50+30+30

【算法分析】

本題轉(zhuǎn)化成模型就是：在一個無向圖中，對于每個點，取一條

和它相關(guān)聯(lián)的邊（如果這樣的邊存在的話），使得取出來的所有邊

的權(quán)和最大。

首先，如果這個圖是不連通的，那么它的各個連通分量之間是

沒有任何聯(lián)系的。對這些連通分量中的問題可以分別獨立地解決，

合并起來就是整個問題的解。所以我們在下面的討論中假定圖是連

通的。

10

直觀地考慮，如果圖中存在度為1的點，那么就把這一點上的

唯一的一條邊分配給這個點（將某條邊“分配”給某個點的含義是：

將這條邊作為和這一點相關(guān)聯(lián)的邊取出來，同時這一點就失效了，

因為和它相關(guān)聯(lián)的其他邊都不能再取了）。如果不存在這樣的點，

那么此時有兩種情況：一種是邊數(shù)等于點數(shù)，那么這個圖就是一個

環(huán)，這時可以取出圖中所有的邊；一種是邊數(shù)大于點數(shù)，那么就可

以把這個圖中權(quán)最小的一條邊直接刪去，因為這條邊“顯然”不會被

取到的。

依據(jù)這樣一個直觀思想，本題可以用貪心法來解決。

貪心算法（用于連通圖）：

1、如果圖中只有一個點，直接結(jié)束算法。

2、如果圖中存在度為1的點，執(zhí)行3；否則轉(zhuǎn)4。

3、任意找一個度為1的點v，將v上的唯一一條邊分配給它。轉(zhuǎn)2。

4、如果圖中的邊數(shù)等于點數(shù)，執(zhí)行5；否則轉(zhuǎn)6。

5、設(shè)圖中的點數(shù)（也就是邊數(shù)）為n。任取一條邊e1，將它分配

給它的兩個端點中的任意一個v1；然后將v1上的另一條邊e2分

配給e2的另一個端點v2；將v2上的另一條邊e3分配給e3的另

一個端點v3；……如此重復(fù)直到將en分配給vn，即圖中所有的

邊都已分配，結(jié)束算法。

6、將圖中權(quán)最小的邊不分配而直接刪去。如果此時圖仍然連通，

則轉(zhuǎn)2；否則對這個圖的兩個連通分量分別執(zhí)行本算法。

11

例6．?dāng)?shù)字游戲

【題目描述】

小W發(fā)明了一個游戲，他在黑板上寫出一行數(shù)字a1，a2，…

an,然后給你m個回合的機會，每個回合你可以從中選一個數(shù)擦除

它，接著剩下來的每個數(shù)字ai都要遞減一個值bi。如此重復(fù)m個

回合，所有你擦除的數(shù)字之和就是你得到的分?jǐn)?shù)。

編程幫小W算算，對于每個給出的an和bn序列，可以得到

的最大得分是多少？

數(shù)據(jù)輸入：

由文件game. in提供輸入數(shù)據(jù)。文件的第1 行一個整數(shù)n（1

≤n≤200），表示數(shù)字的個數(shù)；第二行一個整數(shù)m（1≤m≤n），表示

回合數(shù)；接下來一行有n個不超過10000的正整數(shù)，a1，a2，…

an，表示原始數(shù)字；最后一行有n個不超過500的正整數(shù)，b1，

b2，…bn，表示每回合每個數(shù)字遞減的值。

結(jié)果輸出:

程序運行結(jié)束時，將計算結(jié)果輸出到文件game. out 中。一

個整數(shù)，表示最大可能的得分。

輸入文件示例

輸入：

3

3

12

10 20 30

4 5 6

輸出：

47

【算法分析】

本題上面一排數(shù)是作為被減數(shù)的，若對被減數(shù)采用貪心算法

不一定能得到全局最優(yōu)解。因為被減數(shù)小減數(shù)大，其差小會導(dǎo)致最

大得分少。先運用貪心的思想對第二排減數(shù)進行從大到小排序，再

運用動態(tài)規(guī)劃思想遞推求解。

#include//數(shù)字游戲

using namespace std;

struct XX

{int a,b;

}a[201];

int n,m,f[2][201],i,j;

int comp(const void *a,const void *b)

{

return(*(XX*)b).b-(*(XX*)a).b;

}

int main()

{ freopen ("","r",stdin);

freopen ("","w",stdout);

13

memt(f,0,sizeof(f));

cin>>n>>m;

for (i=1;i<=n;i++) cin>>a[i].a>>a[i].b;

qsort(a+1,n,sizeof(a[0]),comp);

for (i=1;i<=n;i++)

for (j=1;j<=min(i,m);j++)

f[i%2][j]=max(f[(i-1)%2][j],f[(i-1)%2][j-1]+a[i].a-

a[i].b*(j-1));

cout<

return 0;

}

例7．開會問題

某公司的會議日益增多，以至于全公司唯一的會議室都不夠用

了。現(xiàn)在給出這段時期的會議時間表，要求你失單適當(dāng)刪除一些會

議，使得剩余的會議在時間上互不沖突，要求刪除的會議最少。

輸入格式：第1行n,表示有n 個會議。接下來有n行，每行

兩個數(shù)，si，fi表示會議i的起止時間。

輸出格式：僅1行，刪除的最少會議數(shù)d.

N<=500,si,fi為整型數(shù)

注意：會議（1，3）和會議（3，5）是不沖突的，但和會議（2，

5）是沖突的。

14

【算法分析】

題目要求刪除最少的會議，使得剩余的會議在時間上不互相沖

突，這實際上是要求安排最多的在時間上不沖突的會議。由于我們

的目標(biāo)是盡可能多地安排會議，而不管安排了那些會議，所以可采

用以下貪心方法：首先將所有會議按結(jié)束時間從小到大排序，每次

總是安排結(jié)束時間早的會議，這樣不僅安排了一個會議，同時又為

剩余的會議留下盡可能的時間。

例8．智力大沖浪

【題目描述】

小偉報名參加電視臺的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾

多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者m元。

接下來主持人宣布比賽規(guī)則：首先，比賽時間分為n個時段

（n<=500）,它又給出了很多小游戲，每個小游戲都必須在規(guī)定期

限ti前完成（i<=ti<=n）。如果一個游戲不能在規(guī)定期限完成，則要

從獎勵費m元中扣去一部分錢wi，wi 為自然數(shù)，不同的游戲扣去

的錢數(shù)不同。當(dāng)然每個游戲本身都很簡單，保證每個參賽者都能在

一個時段內(nèi)完成，而且都必須從整數(shù)段開始。主持人只是想考考每

個參賽者如何安排組織自己做游戲的順序。問小偉最多能得到多少

錢？

輸入：第1行為m，表示一開始獎勵給每個參賽者的錢數(shù)

第2行為n表示有n個小游戲。

15

第3行有n個數(shù)，分別表示n個游戲規(guī)定完成的期限

第4行有n個數(shù)，分別表示n個游戲不能在規(guī)定期限完成的

扣款數(shù)

輸出：僅一個數(shù)，表示小偉能贏得最多的錢數(shù)。

樣例：

輸入：

10000

7

4 2 4 3 1 4 6

70 60 50 40 30 20 10

輸出：

9950

【算法分析】

因為不同的小游戲不能準(zhǔn)時完成時具有不同的扣款權(quán)數(shù)，而

且是最優(yōu)解問題，所以本題很容易就想到了貪心法。貪心的主要思

想是要讓扣款數(shù)值大的盡量準(zhǔn)時完成。這樣我們就先把這些任務(wù)按

照扣款的數(shù)目進行排序，把大的排在前面，先進行放置。假如罰款

最多的一個任務(wù)的完成期限是k，我們應(yīng)該把它安排在哪個時段完

成呢？應(yīng)該放在第k個時段，因為放在1～k任意一個位置，效果

都是一樣的。一旦出現(xiàn)一個不可能在規(guī)定時限前完成的任務(wù)，則把

其扔到最大的一個空時間段，這樣必然是最優(yōu)的，因為不能完成的

任務(wù)，在任意一個時間段中罰款數(shù)目都是一樣的.

16

本題也可以有另外一種貪心算法，即先把所有的數(shù)據(jù)按照結(jié)束

時間的先后排序，然后從前向后掃描。當(dāng)掃描到第n個時段，發(fā)現(xiàn)

里面所分配任務(wù)的結(jié)束時間等于n-1，那么就說明在前面這些任務(wù)

中必須舍棄一個，于是再掃描第1～n這n個時段，挑出一個最小

的去掉并累加扣款值，然后再去調(diào)整排列順序，讓后面的元素填補

前面的空缺，

例9．合并果子（）。

【題目描述】

在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子

的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每

一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆

果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就

只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所

耗體力之和。

因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡

可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類

數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多

耗費的體力最少，并輸出這個最小的體力耗費值。

例如，有3種果子，數(shù)目依次為1、2、9。可以先將1、2堆合并，

新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，

17

又得到新的堆，數(shù)目為12，耗費體力為12。所以多多總共耗費體

力15=3+12。可以證明15為最小的體力耗費值。

【輸入】

輸入文件包括兩行。第一行是一個整數(shù)n(1≤n≤10000)，表

示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)

ai(1≤ai≤20000)是第i種果子的數(shù)目。

【輸出】

輸出文件包括一行，這一行只包含一個整數(shù)，也就是最小

的體力耗費值。輸入數(shù)據(jù)保證這個值小于231。

【樣例輸入】

3

1 2 9

【樣例輸出】

15

【數(shù)據(jù)規(guī)模】

對于30%的數(shù)據(jù)，保證有n≤1000；

對于50%的數(shù)據(jù)，保證有n≤5000；

對于全部的數(shù)據(jù)，保證有n≤10000。

【算法分析】

此題用貪心法。先將果子數(shù)排序，取其中最小的兩堆合并，得

到一個新堆；再排序，再取其中最小的兩堆合并……直到只剩一堆。

為盡快出解，排序的速度顯得格外重要，可用堆排序算法。

18

例10． 建筑搶修（）。

【題目描述】

小剛在玩JSOI提供的一個稱之為“建筑搶修”的電腦游戲。經(jīng)

過了一場激烈的戰(zhàn)斗，T部落消滅了所有Z部落的入侵者。但是T

部落的基地里已經(jīng)有N個建筑設(shè)施受到了嚴(yán)重的損傷，如果不盡

快修復(fù)的話，這些建筑設(shè)施將會完全毀壞。

現(xiàn)在的情況是：T部落基地里只有一個修理工人。雖然他能瞬

間到達(dá)任何一個建筑，但是修復(fù)每個建筑都需要一定的時間。同時，

修理工人修理完一個建筑才能修理下一個建筑，不能同時修理多個

建筑。如果某個建筑在一段時間之內(nèi)沒有完全修理完畢，這個建筑

就報廢了。

你的任務(wù)是幫小剛合理制定一個修理順序，以搶修盡可能多的建

筑。

【輸入】

輸入文件第一行是一個整數(shù)N，N行每行兩個整數(shù)T1、T2描述一

個建筑：修理這個建筑需要T1秒，如果在T2秒之內(nèi)還沒有修理

完成，這個建筑就報廢了。

【輸出】

輸出文件只有一行，是一個整數(shù)S，表示最多可以搶修S個建筑。

N＜150000; T1＜T2＜maxlongint

19

【樣例輸入】

4

100 200

200 1300

1000 1250

2000 3200

【樣例輸出】

3

【算法分析】

貪心 O(N Log N) + 高級數(shù)據(jù)結(jié)構(gòu)。很容易想到動態(tài)規(guī)劃。按

截止時間排序，維護隊列q，如果能插入就插入，如不能插入，就

把一個花費時間最大的替換下來

貪心算法和貪心思想看似簡單，真正完全掌握要下一番功夫。

和任何優(yōu)秀算法一樣，貪心算法也有它的局限性，用不對會丟很多

解，用得好，在編程中能起到事半功倍的效果。

有不對之處請指正，謝謝大家！

20