谈贪心算法

谈谈贪心算法

例1.背包问题

【题目描述】

这是一大家很熟悉的背包问题。给定n种货物和一个载重量为

m的背包。已知第i种货物的重量为wi ,其总价值为pi，编程

确定一个装货方案，使得装入背包中货物的总价值最大。输出

此总价值和装货方案。

【算法分析】

0，1背包问题对每种物品只有两种选择：选和不选，可用动

态规划解决。而背包问题，可以选择物品的一部分装载，这样就可

以把背包装满，用贪心算法可求得最优解。采用贪心标准是：选择

单位重量价值高的货物优先装入，这样才能保证背包中所装货物总

价值最大。而0，1背包用贪心算法却不能得到整体最优，为什么

呢？我们来看一个例子：

有一背包容

量为50千克，有三种货物：

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

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

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

1

20

20

10

总价值：（用贪心算法）

80+100+60=240

对于0，1背包问题，贪心选择之所以不能得到最

优解是因为它无法保证最终将背包装满，部分背包的 闲置使单位

重量背包空间的价值降低。

例2．排队问题

【题目描述】

在一个医院B 超室，有n个人要做不同身体部位的B超，

已知每个人需要处理的时间为ti，（0）,请求出一种排列次序，

使每个人排队等候时间总和最小。

输入数据：第1行一个正整数n（你<=10000》，第2行有n

2

个不超过 1000的正整数ti.

输出要求：n个人排队时间最小总和。

输入输出样例

输入：4

5 10 8 7

输出：

67

【算法分析】

本题贪心算法：n个人时间从小到大排序，就是这n个人最佳

排队方案。求部分和的和即为所求。

反证法证明：假设有最优解序列：s1,s2…sn,如s1不是最小

的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的

人无影响，对sk之前的人等待都减少了，(s1-sk)>0,从而新的序列

比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证

s2…sn依次最小。

例3．:数列极差问题

【题目描述】

在黑板上写了N个正整数做成的一个数列，进行如下操作：

每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，

如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到

3

的数中，最大的max，最小的为min，则该数列的极差定义为

M=max-min。

编程任务：对于给定的数列，编程计算出极差M。

输入输出样例：

输入：

4

2 1 4 3

输出：

13

【算法分析】

当看到此题时，我们会发现求max与求min是两个相似的过

程。若我们把求解max与min的过程分开，着重探讨求max的问

题。

下面我们以求max为例来讨论此题用贪心策略求解的合理

性。

讨论：假设经（Ｎ－3）次变换后得到３个数：a ,b , max＇（max＇

≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后

所得的最大值，此时有两种求值方式，设其所求值分别为 z1，z2，

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

+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的

３个数为：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换

4

后的最大值，即ｍ＜max＇则此时所求得的最大值为：

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

ｍ）＞０ 所以此时不为最优解。

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

（ｋ－１）次变换后所得值最大（符合贪心策略的特点2），在进

行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的

两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合贪心

策略特点1），因此此题可用贪心策略求解。在求ｍin时，我们只

需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用 ｆ：ｐ←

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

这是一道两次运用贪心策略解决的一道问题，它要求选手有较

高的数学推理能力。

例4．整数区间

【题目描述】

我们定义一个整数区间[a,b],a,b是一个从a开始至b 结束的

连续整数的集合。编一个程序，对给定的 n个区间，找出满足下

述条件的所含元素个数最少的集合中元素的个数：对于所给定的每

一个区间，都至少有两个不同的整数属于该集合。(1<=n<=10000,

0<=a<=b<=1000)

输入输出格式：

输入：第一行一个正整数n，接下来有n行，每行给定一个区

5

间的a,b值

输出：一个正整数，即满足条件的集合所包含的最少元素个数

输入输出样例

输入： 输出：

4 4

3 6

2 4

0 2

4 7

【算法分析】

本题数据规模较大，用搜索做会超时，而动态规划无从下手。

考虑贪心算法。题目意思是要找一个集合，该集合中的数的个数既

要少又要和所给定的所有区间有交集。（每个区间至少有两个该集

合中的数）。我们可以从所给的区间中选数，为了选尽量少的数，

应该使所选的数和更多的区间有交集这就是贪心的标准。一开始将

所有区间按照右端点从小到大排序。从第一个区间开始逐个向后检

查，看所选出的数与所查看的区间有无交集，有两个则跳过，只有

一个数相交，就从当前区间中选出最大的一个数（即右端点），若

无交集，则从当前区间选出两个数，就（右端点，右端点-1），直

至最后一个区间。

#include //整数区间问题

using namespace std;

6

struct prince{

int left,right;//区间左右端点

}a[10000];

int n;

int result;//存放结果中的数

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);//按区间右端点由小到大排序

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

【题目描述】

在一片古老的大地上，虽然商业已经非常繁荣，但是那里的人

们仍然延续着古老的交易方式。他们牵着骆驼在城市之间往来奔

波，贩运成批的商品，换来一袋袋的金币。

这片大陆上有N个城市，编号为1……N。在一些城市之间有

路可通，有路就有商队。但是在不同的城市之间经商所得的收益不

同，在下面的这个N=4的例子中，在城市1和城市2之间进行一

次交易可以获得40枚金币，在城市2和3之间交易一次可以获得

50枚金币，等等。

8

30

3

1

40 50 20

30

4

2

在任意两个城市之间，这样的交易只能进行一次。因为你第二

次贩运你的商品时，人们对它们就不会感兴趣了。

现在你只身来到这个大陆上，用有限的资金在每个城市中购买

了一支商队。你需要想办法让你的这N支商队给你带来最大的经

济收益。

任务说明

给出这个大陆的地图和每两个城市之间的贸易值（如果这两个

城市之间有路可通的话），你需要指挥你的N支商队进行一次经商，

使得这N支商队在这次经商中获得的总收益最大。注意：你的每

支商队只能进行一次交易，即它们只能从它们所在的城市到达一个

相邻的城市。当然，它们也可以不进行任何交易。

输入数据

输入文件的第一行有两个整数N（1  N  100）、M（M  0），

分别表示这个大陆上的城市数和道路数。

接下来有M行，每行包括三个整数i、j（1  i,j  N且i  j）、

v(1  V  10000)，表示一条道路的信息。其中i和j表示这条路在

城市i和城市j之间，v表示沿着这条路进行一次交易所得的收益。

i和j的顺序是无关的，并且任意两个城市之间最多存在一条路。

9

输出数据

你的输出文件应该2行，第1行包含N个整数。其中第k个

整数表示你在城市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

【算法分析】

本题转化成模型就是：在一个无向图中，对于每个点，取一条

和它相关联的边（如果这样的边存在的话），使得取出来的所有边

的权和最大。

首先，如果这个图是不连通的，那么它的各个连通分量之间是

没有任何联系的。对这些连通分量中的问题可以分别独立地解决，

合并起来就是整个问题的解。所以我们在下面的讨论中假定图是连

通的。

10

直观地考虑，如果图中存在度为1的点，那么就把这一点上的

唯一的一条边分配给这个点（将某条边“分配”给某个点的含义是：

将这条边作为和这一点相关联的边取出来，同时这一点就失效了，

因为和它相关联的其他边都不能再取了）。如果不存在这样的点，

那么此时有两种情况：一种是边数等于点数，那么这个图就是一个

环，这时可以取出图中所有的边；一种是边数大于点数，那么就可

以把这个图中权最小的一条边直接删去，因为这条边“显然”不会被

取到的。

依据这样一个直观思想，本题可以用贪心法来解决。

贪心算法（用于连通图）：

1、如果图中只有一个点，直接结束算法。

2、如果图中存在度为1的点，执行3；否则转4。

3、任意找一个度为1的点v，将v上的唯一一条边分配给它。转2。

4、如果图中的边数等于点数，执行5；否则转6。

5、设图中的点数（也就是边数）为n。任取一条边e1，将它分配

给它的两个端点中的任意一个v1；然后将v1上的另一条边e2分

配给e2的另一个端点v2；将v2上的另一条边e3分配给e3的另

一个端点v3；……如此重复直到将en分配给vn，即图中所有的

边都已分配，结束算法。

6、将图中权最小的边不分配而直接删去。如果此时图仍然连通，

则转2；否则对这个图的两个连通分量分别执行本算法。

11

例6．数字游戏

【题目描述】

小W发明了一个游戏，他在黑板上写出一行数字a1，a2，…

an,然后给你m个回合的机会，每个回合你可以从中选一个数擦除

它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个

回合，所有你擦除的数字之和就是你得到的分数。

编程帮小W算算，对于每个给出的an和bn序列，可以得到

的最大得分是多少？

数据输入：

由文件game. in提供输入数据。文件的第1 行一个整数n（1

≤n≤200），表示数字的个数；第二行一个整数m（1≤m≤n），表示

回合数；接下来一行有n个不超过10000的正整数，a1，a2，…

an，表示原始数字；最后一行有n个不超过500的正整数，b1，

b2，…bn，表示每回合每个数字递减的值。

结果输出:

程序运行结束时，将计算结果输出到文件game. out 中。一

个整数，表示最大可能的得分。

输入文件示例

输入：

3

3

12

10 20 30

4 5 6

输出：

47

【算法分析】

本题上面一排数是作为被减数的，若对被减数采用贪心算法

不一定能得到全局最优解。因为被减数小减数大，其差小会导致最

大得分少。先运用贪心的思想对第二排减数进行从大到小排序，再

运用动态规划思想递推求解。

#include//数字游戏

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．开会问题

某公司的会议日益增多，以至于全公司唯一的会议室都不够用

了。现在给出这段时期的会议时间表，要求你失单适当删除一些会

议，使得剩余的会议在时间上互不冲突，要求删除的会议最少。

输入格式：第1行n,表示有n 个会议。接下来有n行，每行

两个数，si，fi表示会议i的起止时间。

输出格式：仅1行，删除的最少会议数d.

N<=500,si,fi为整型数

注意：会议（1，3）和会议（3，5）是不冲突的，但和会议（2，

5）是冲突的。

14

【算法分析】

题目要求删除最少的会议，使得剩余的会议在时间上不互相冲

突，这实际上是要求安排最多的在时间上不冲突的会议。由于我们

的目标是尽可能多地安排会议，而不管安排了那些会议，所以可采

用以下贪心方法：首先将所有会议按结束时间从小到大排序，每次

总是安排结束时间早的会议，这样不仅安排了一个会议，同时又为

剩余的会议留下尽可能的时间。

例8．智力大冲浪

【题目描述】

小伟报名参加电视台的智力大冲浪节目。本次挑战赛吸引了众

多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。

接下来主持人宣布比赛规则：首先，比赛时间分为n个时段

（n<=500）,它又给出了很多小游戏，每个小游戏都必须在规定期

限ti前完成（i<=ti<=n）。如果一个游戏不能在规定期限完成，则要

从奖励费m元中扣去一部分钱wi，wi 为自然数，不同的游戏扣去

的钱数不同。当然每个游戏本身都很简单，保证每个参赛者都能在

一个时段内完成，而且都必须从整数段开始。主持人只是想考考每

个参赛者如何安排组织自己做游戏的顺序。问小伟最多能得到多少

钱？

输入：第1行为m，表示一开始奖励给每个参赛者的钱数

第2行为n表示有n个小游戏。

15

第3行有n个数，分别表示n个游戏规定完成的期限

第4行有n个数，分别表示n个游戏不能在规定期限完成的

扣款数

输出：仅一个数，表示小伟能赢得最多的钱数。

样例：

输入：

10000

7

4 2 4 3 1 4 6

70 60 50 40 30 20 10

输出：

9950

【算法分析】

因为不同的小游戏不能准时完成时具有不同的扣款权数，而

且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思

想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按

照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款

最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完

成呢？应该放在第k个时段，因为放在1～k任意一个位置，效果

都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把

其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的

任务，在任意一个时间段中罚款数目都是一样的.

16

本题也可以有另外一种贪心算法，即先把所有的数据按照结束

时间的先后排序，然后从前向后扫描。当扫描到第n个时段，发现

里面所分配任务的结束时间等于n-1，那么就说明在前面这些任务

中必须舍弃一个，于是再扫描第1～n这n个时段，挑出一个最小

的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补

前面的空缺，

例9．合并果子（）。

【题目描述】

在一个果园里，多多已经将所有的果子打了下来，而且按果子

的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每

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

果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就

只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所

耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽

可能地节省体力。假定每个果子重量都为1，并且已知果子的种类

数和每种果子的数目，你的任务是设计出合并的次序方案，使多多

耗费的体力最少，并输出这个最小的体力耗费值。

例如，有3种果子，数目依次为1、2、9。可以先将1、2堆合并，

新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，

17

又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体

力15=3+12。可以证明15为最小的体力耗费值。

【输入】

输入文件包括两行。第一行是一个整数n(1≤n≤10000)，表

示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数

ai(1≤ai≤20000)是第i种果子的数目。

【输出】

输出文件包括一行，这一行只包含一个整数，也就是最小

的体力耗费值。输入数据保证这个值小于231。

【样例输入】

3

1 2 9

【样例输出】

15

【数据规模】

对于30%的数据，保证有n≤1000；

对于50%的数据，保证有n≤5000；

对于全部的数据，保证有n≤10000。

【算法分析】

此题用贪心法。先将果子数排序，取其中最小的两堆合并，得

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

为尽快出解，排序的速度显得格外重要，可用堆排序算法。

18

例10． 建筑抢修（）。

【题目描述】

小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏。经

过了一场激烈的战斗，T部落消灭了所有Z部落的入侵者。但是T

部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽

快修复的话，这些建筑设施将会完全毁坏。

现在的情况是：T部落基地里只有一个修理工人。虽然他能瞬

间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，

修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个

建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑

就报废了。

你的任务是帮小刚合理制定一个修理顺序，以抢修尽可能多的建

筑。

【输入】

输入文件第一行是一个整数N，N行每行两个整数T1、T2描述一

个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理

完成，这个建筑就报废了。

【输出】

输出文件只有一行，是一个整数S，表示最多可以抢修S个建筑。

N＜150000; T1＜T2＜maxlongint

19

【样例输入】

4

100 200

200 1300

1000 1250

2000 3200

【样例输出】

3

【算法分析】

贪心 O(N Log N) + 高级数据结构。很容易想到动态规划。按

截止时间排序，维护队列q，如果能插入就插入，如不能插入，就

把一个花费时间最大的替换下来

贪心算法和贪心思想看似简单，真正完全掌握要下一番功夫。

和任何优秀算法一样，贪心算法也有它的局限性，用不对会丢很多

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

有不对之处请指正，谢谢大家！

20