第 33 章
贪心算法
贪心算法一般来说是解决“最优问题”，具有编程简单、运行效率高、空间复杂度低
等特点。是程序竞赛中的一个有力武器，受到广大同学们的青睐。
贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有 n 个输入，它的
解是由这 n 个输入的某个子集组成，并且这个子集必须满足事先给定的条件。这个条件称
为约束条件。而把满足约束条件的子集称为该问题的可行解。这些可行解可能有多个。为
了衡量可行解的优劣，事先给了一个关于可行解的函数，称为目标函数。目标函数最大（或
最小）的可行解，称为最优解。
贪心算法的正确性
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
虽然不容易，但一些常见的方法还是值得总结的。
1．构造法
根据描述的算法，用贪心的策略，依次构造出一个解，可证明一定是合法的解。即用
贪心法找可行解。
2．反证法
用贪心的策略，依次构造出一个解 S1。假设最优解 S2 不同与 S1，可以证明是矛盾的。
从而 S1 就是最优解。
3．调整法
用贪心的策略，依次构造出一个解 S1。假设最优解 S2 不同与 S1，找出不同之处，在
不破坏最优性的前提下，逐步调整 S2，最终使其变为 S1。从而 S1 也是最优解。
3.1 构造法
构造法就是从一个空的解开始，根据贪心策略，逐步将新的内容加入原有的解中，直
到满足
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
或无法将新的元素加入为止。也可以将使用相反的手段，即先将整个解设定为
一个最大的集合，然后，用贪心策略逐步从原有解中取出元素，直至满足要求或无法取出
元素为止。本节例题将介绍第一种贪心的例子。
3.1.1 〖案例 1〗订票
一家票务办公室为音乐会售票。它们以出售某一固定数量的连号票（简称套票）来替
代常见的单张票销售。票务办收到了大量的购票订单。套票的订单以该套票中最小的座位
号作为标识。然而票务办并不能满足所有的订单，而且如果他们完全按照观众的要求来分
·60·
ACM 程序设计
培训
焊锡培训资料ppt免费下载焊接培训教程 ppt 下载特设培训下载班长管理培训下载培训时间表下载
教程
配座位，就会出现很多空位。为此票务办采取了如下的座位分配和价格策略：
如果一个订单被接受且完全按照观众的要求安排座位，那么观众就要付全价(每套票 2
petaks)；如果一个订单虽被接受但是至少有一个座位与观众的要求不同，那么顾客只需付
半价（每套票 1 petaks)。
现在的目标是怎样才能使总收入最高。编写程序计算能够获得的最大收入（子任务 A）；
并给出实现这一收入所选择的订单和座位分配法（子任务 B）。
文件 ticket.in 的第一行含有两个整数：
座位总数 M (1 ≤ M ≤ 30000)和每套票所含的座位数 L (1 ≤ L ≤ 100)。座位从 1
到 M 编号。
第二行是收到的订单数 N (1 ≤ N ≤ 100000)。
第三行包含 N 个整数，确定了订单的详细信息。这一行的第 i 个数 z (1 ≤ z ≤
M-L+1)，
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示第 i 份订单要求套票座位从 z 到 z+L-1。
文件 ticket.out 的第一行包含一个整数 S，为能够获得的最大收入（子任务 A）。
第二行是最后接受的订单数 Q。
接下来的 Q 行表示座位分配方式（子任务 B）。每行都有两个整数 x y。表示观众 x 分
到的座位从 y 号开始。注意应按座位号的增序排列这 Q 行。
如果有多种实现的可能，仅需输出一种即可。
service.in
20 3
7
4 2 10 9 16 15 17
service.out
9
6
4 1
1 4
2 7
3 10
6 13
5 16
·61·
第 3 章 贪心算法
样例分析
订单号 订座号 分配结果
（1） 4 5 6 √
（2） 2 3 4 →7 8 9
（3） 10 11 12 √
（4） 9 10 11 →1 2 3
（5） 16 17 18 √
（6） 15 16 17 →13 14 15
（7） 17 18 19
7 个订单, 3 座位/套 最大收入 9, 接受 6 个订单
参考解答与算法分析
这里采用贪心法求解该问题。算法分为 3 个步骤。
第一步：试图分配尽可能多的全价套票。
贪心法按照座位号递减的次序来处理这些订单。只要可行就为其分配座位。将这样得
到的座位表记为 S1。
第二步：调整 S1 以减少浪费。这意味着如果要用订单 p 来代替 p1，就要求 p< p1，并
且 p mod L（L 为每套票的座位数）取最小。这样就可以得到 S2。
第三步：将全价票之间的空位用半价票来填满。最后得到的座位表是 S3。
我们要证明，S3 是最优解。
图 3. 1
设 S 为一个能产生最大收入的最优解，我们用一般的方法来证明上述贪心过程的正确性。
我们在保持总收入不变的前提下逐步修改 S 以得到 S3。令 k 为 S1 中全价票的订单数，
我们先证明存在 k 套全价票的最优解情形。S 中全价票的数量至多为 k。假设 S 中的全价票
数目小于 k，如果 S1 中的一份订单 pi 和 S 中的全价票订单没有冲突，那么 pi 至多与两份半
价票发生冲突，于是我们就在 S 中用一份全价 pi 来替换那两份半价票，这样不会引起收入
的改变。这便是图 3.2-a 的情形。重复以上步骤，直到 S1 中的每份套票都至少和 S 中的一份
全价套票冲突。如果 S 中的全价票数仍然少于 k，就会出现图 3.2-b 的情形。那么就把 S 中
凡是与 S1 中的两份票任一个冲突的部分都去掉，而用 S1 中的那两份票来替代 S 中移去的部
分。
·62·
ACM 程序设计培训教程
图 3.2
我们可以假定，半价票将被尽可能的往左移。令 p1 为 S1 中最左边的全价票（的第一
个座位号）；q1 为 S3 中，r1 为 S 中相应的含义。注意 q1 必须要碰到 r1。如果 q1< r1,那么
q1 订单不会与 S 中的半价票冲突，因为在这种情形下，浪费将少于 S3 中第一个全价订单
（q1 在 S3 中的空余位更少），我们在算法的第二步中就会选择它。因此我们用 q1 来代替
S 中的 r1。这就是图 3.4 中的情形。
图 3.3
图 3.4
现在我们来看 q1 > r1 的情形，令 k 为满足
a = k*L< r1 的最大整数。
同时，取 b 为满足 a
Lend then begin
Sol:=Sol+(Start[S[k]]-free) div L+1;
free:=Start[S[k]]+L;
inc(k);
Lend:=Start[S[k]];
gap:=m;
end;
if (free<=Start[R[i]])and((Start[R[i]]-free) mod Ln then Sol:=n;
assign(OutF, ’ticket.out’); rewrite(OutF);
writeln(OutF, Sol+fn);
writeln(OutF, Sol);
{3. step: fill in the gaps with half-price orders}
for i:=1 to m do Sch[i]:=0;
for i:=1 to fn do
for k:=Start[S[i]] to Start[S[i]]+L-1 do
Sch[k]:=S[i];
free:=1; i:=1;
while i<=n do begin
if free+L-1>m then break;
if Sch[Start[R[i]]]=R[i] then begin
inc(i); continue;
end;
k:=Sch[free+L-1];
if (Sch[free]=0)and(k=0) then begin
Sch[free]:=R[i];
free:=free+L;
inc(i);
end else
free:=Start[k]+L;
end {while i};
k:=1;
while k<=m do begin
if Sch[k]>0 then begin
writeln(OutF, Sch[k],’ ’,k);
k:=k+L;
end else begin
inc(k);
end;
end;
close(OutF);
End.
3.2 反证法
反证法就是先列出可能的解，然后运用贪心策略对其进行验证，由于贪心的验证速度
快，配合二分枚举等策略可大大提高程序的执行效率。本节就是二分枚举和贪心反证的例
子。
·66·
ACM 程序设计培训教程
3.2.1 〖案例 2〗电梯
Zsoft 公司是一家位于高科大厦的软件公司。而且大厦里的工作人员工作非常努力。但
是大厦里的电梯经常让他们发疯。为什么？原来高科大厦里只有一部电梯，但这里确有属
百个公司。每天早上，人们必须浪费很多时间等电梯，Zsoft 里有一个聪明的家伙，想要改
变这种状况。他想找到一种方法，让电梯工作的更有效。不过这可并非易事。
高科大厦有 H 层。电梯上升一层需要 4 秒时间。也就是说，电梯从 1 楼运行到 n 楼需
要(n-1)*4 秒，如果中间不停的话。而电梯停一次需要 10 秒时间。所以，考虑电梯停留时
间的话，从一楼运行到 n 楼需要 cost (n-1)*4+(n-2)*10 秒。另一方面,员工走楼梯(上楼或下
楼)，一层需要 20 秒。走 n 层楼需要花费(n-1)*20 秒的时间。显然，这不是个好主意。所
以，一些人选择坐电梯到离他们办公室最近的一层。
经过很长时间的思考，这个人终于找到一种方法，以改变这种状况。他把自己的想法
告诉开电梯的人：首先，开电梯的人向人们询问他们要去的楼层。然后他设计一种停留方
案，使最后一个人到达他办公室所在楼层的时间最小化。举例来说，如果电梯需要停在 4
楼、5 楼和 10 楼，停留的计划会是：电梯停在 4 楼和 10 楼。因为电梯从 1 楼到 4 楼需要
花 3*4=12 秒的时间，然后，到 5 楼的人步行 1 层，需要花费 3*4+20=32 秒的时间，电梯
经过 10 秒的停留后，运行到 10 楼需要 3*4+10+6*4=46 秒的时间。也就是，最后一个到达
的人需要花费 46 秒的时间。这对所有人都是一个好主意。
现在，你被要求写一个程序，以帮助开电梯的人制订停留计划，以最小化最后一个人
到达他所在楼层的时间。
输入包含多组数据，每组数据在单独的一行上，如下所示：
n f1 f2 ... fn
其含义为，总共有 n 层需要停留，n=0 时程序结束。然后，f1 f2 … fn 是电梯需要停留
的楼层(1<=n<=30000, 2<=f1< f2 ... fn<=30000) 。数字之间用一个空格隔开。
对每一组数据，在单独的一行上输出最后一个人到达所需的时间。
3 4 5 10
1 2
0
46
4
·67·
第 3 章 贪心算法
这个题目跟 Advanced Causal Measurements (ACM)(POJ 1727)是同一个思路，对答案进
行枚举即可。
对于每个给定的时间 t，我们可以使用贪心法确定是否可以在时间 t 内让所有人都到达
目的层。显然，每一次电梯都尽量往上开。
比如说现在第 i 层有人要下，电梯应该在哪一层停靠呢？假设电梯已经停靠了 n 次，
那么我们让电梯在第 j=[(t-10*n+20*i+4)/24]层停靠即可。注意此时若 j
#include
const int M=30001;
bool ind[M];
int n;
int solve(int t){ // 判定时间 t 之内所有人是否都能到达目标层
int i,j,now=0,num=0;
i=t/20+2; // i 层以下的人直接走楼梯，哈哈
while(i<=n)
{ while(i<=n && ind[i]==false){ // i 层没人时不用理
i++;
}
if((i-1)*4+10*num>t)
return 0; // 电梯无法在时间 t 之内到达 i 层
j=(t-10*num+20*i+4)/24; // 电梯在第 j 层停靠最好
i=(t-10*num+16*j+4)/20+1; // 电梯 i 层以下的都已经搞定
num++;
·68·
ACM 程序设计培训教程
}
return 1;
}
main(){
int i,j,min,max,mid,t;
// freopen("data.txt","r",stdin);
while(1)
{ scanf("%d",&t);
if(t==0) break;
memset(ind,false,sizeof(ind));
n=-1; // 读入数据
for(i=0;in) n=j;
ind[j]=true;
}
// 二分法，查找区间为 [min,max]，其中 min 总是不可行的，max 则为可行解
min=0;max=14*(n-1);
while(min
#include
int h[1000000];
// 保存每个格子的高度值，因不知 m 和 n 的范围，故设的比较大
int cmp(const void *a, const void *b){
return *((int *)a) - *((int *)b);
}
main(){
int t, m, n, nn;
double x, hw;
int i;
t = 0;
while(1){
//输入
scanf("%d%d", &n, &m);
if(n == 0 && m == 0) break;
t++;
nn = m * n;
for(i = 0; i < nn; i++){
scanf("%d", &h[i]);
}
scanf("%lf", &x);
//排序
qsort(h, nn, sizeof(int), cmp);
·71·
第 3 章 贪心算法
i = 0;
hw = h[0];
if(x > 0){
for(i = 1; i < nn; i++){
//在高度相等的情况下，扩大水面面积
while(i < nn && h[i] == h[i - 1]){
i++;
}
if(i == nn || x <= 100* i * (h[i] - h[i - 1])) break;// 若剩
下的水不够使水面达到下一格子的高度，退出
x -= i * (h[i] - h[i - 1])*100;
}
hw = h[i - 1];
}
if(x > 0){ // 若剩下水，就把它铺在当前的范围上
while(i < nn && h[i] == h[i - 1]){
i++;
}
hw += x / i /100;
}
// 输出结果
printf("Region %d\n", t);
printf("Water level is %.2f meters.\n", hw);
printf("%.2f percent of the region is under water.\n\n", i * 100 /
double(nn));
}
}
3.3.2 〖案例 4〗埃及分数
埃及同中国一样，也是世界上文明的古国之一。古埃及人处理分数与众不同，他们一
般只用分子为 1 的分数，例如：用 1／3＋1／15 来表示 2／5，用 1／4＋1／7＋1／28 表示
3／7，等等。设计一个程序，把一个真分数表示为埃及分数之和的形式。
问题分析：
所谓埃及分数，是指分子为 1 的形式。古代埃及有一个非常奇怪的习惯，他们喜欢把
一个分数表示为若干个分子为 1 的分数之和的形式。如，7/8=1/2+1/3+1/24。
下面介绍其中一种算法――贪心算法。贪心算法是由数学家菲波那契提出的，基本思
想是：
设某个真分数的分子为 A，分母为 B；
把 B 除以 A 的商的整数部分加 1 后的值作为埃及分数的某一个分母；
·72·
ACM 程序设计培训教程
将 A 乘以 C 减去 B 作为新的 A；
将 B 乘以 C 作为新的 B；
如果 A 大于 1 且能整除 B，则最后一个分母为 B/A；
如果 A＝1，则最后一个分母为 B；
否则转步骤（2）。
如：7/8=1/2+1/3+1/24
解题步骤：
用变量 A 表示分子，变量 B 表示分母；
C=B\A+1
A=A*C-B,B=B*C
打印 1/C
若 A>1 且 B/A=B\A，则 C=B/A
若 A＝1，则 C=B,打印 1/C
转步骤（2）。
程序清单：
CLS
DO
INPUT "a,b=";a,b
LOOP UNTIL a1 THEN PRINT"+";
LOOP WHILE a>1
PRINT"+1";b
END
3.3.3 〖案例 2〗数的划分的研究
问题描述
求把一个整数 n 无序划分成 k 份互不相同的正整数之和的方法总数。
分析
我们其实可以将这题转化一下.因为我们知道我们在划分时只要按不下降排列就不会
有重复.并且每一份都不为 0.我们可以形象的把 n的k-自然数剖分看作把 n块积木堆成 k列，
且每列的积木个数依次递增，也就是这 n 块积木被从左到右积木被堆成了"楼梯状"。比如，
下图 3.5 是 10 的几种 4-剖分。
·73·
第 3 章 贪心算法
图 3.5
现在，我们不妨把这三个图顺时针旋转 90 度，成为：
图 3.6
对于这道题我们很容易可以想到一种状态表示方法,即用 F(I,J,K)来表示把 J 无序划分
成 I 份其中最大为 K的划分方案数.那么,它就等于把 J-K 无序划分成 I-1 份,其中最大不超过
K 的划分方案数，状态转移方程就是
对应的 pascal 程序如下：
procedure dp;
var i,j,k,l:integer;
begin
assign(output,outputfile);
rewrite(output);
f[0,0,0]:=1;
for i:=1 to m do
for j:=i to n do
for k:=1 to j do
for l:=0 to k do
inc(f[i,j,k],f[i-1,j-k,l]);
for i:=1 to n do inc(count,f[m,n,i]);
writeln(count);
close(output);
end;
但是如果我们再把上图逆时针翻转 90 度，那么其实也就等于先在最下一行各摆上一块
积木接下来也就是把 I-J 块积木放上去,并要保持楼梯状.我们可以发现其实上就是把 I-J 无
·74·
ACM 程序设计培训教程
序拆分成 1～K 份。那么我们可以得到如下动态转移方程
procedure dp;
var i,j,k:integer;
begin
f[0,0]:=1;
for i:=1 to n do
for j:=1 to m do
if j<=i then
for k:=0 to j do
inc(f[i,j],f[i-j,k]);
assign(output,outputfile);
rewrite(output);
writeln(f[n,m]);
close(output);
end;
我们还可以把上述式子继续简化，因为我们发现，其实
F[I-1,J-1]=
那么我们在计算 F[I,J]的时候就可以只做 F[I,J]=F[I-1,J-1]+F[I-J,J]一次简单的加法运算
就可以了，这样可以大大减少时间。
procedure dp;
var i,j,k:integer;
begin
f[0,0]:=1;
for i:=1 to n do
for j:=1 to m do
if i>=j then f[i,j]:=f[i-j,j]+f[i-1,j-1];
assign(output,outputfile);
rewrite(output);
writeln(f[n,m]);
close(output);
end;
其实对于这题我们还可以继续优化,例如用滚动数组的方法使存处空间减少,这里就不
再累赘了。
这里还想介绍一种更容易的做法。
若用 F(I,J)表示把 I 无序划分成 J 份的方案数，则 F（5,2）=（{1,4},{2,3}）;F（6,3）=
（{1,1,4},{1,2,3},{2,2,2}）
你一定会发现如果把 I 无序划分为 J 份,那么它的前几个划分一定等于把 I-1 无序划分
成 J-1 份每份前面加 1 的方案数。
·75·
第 3 章 贪心算法
那么后面那一部拆分方案又会等于什么呢?我们不妨将后面每一份中的每一个数减 1,
我们会发现它与 F(I-J,J)是一一对应的。
证明如下：
我们将一个自然数 I 划分为 K 份，为了避免重复，习惯于从小到大地划分。我们将数
I 分为 K 份的方法数记作 F（I，K），可知：F（I，K）=F（I-K，K）+F（I-1，K-1）
证明：
设集合{A}为 I 的所有划分方案的第一项，0〈A〈=（I DIV K），设每一种划分方案的
以后 K-1 个数为 A+D1，A+D2，A+D3 „A+Dk-1，Di≤Di+1，于是：
D 的不下降排列数即 I 的首项是 A 的不同划分数 。
同理，设{B}为 I-K的划分方案的首项集合，以后的 K-1 个数是 B+C1，B+C2„ B+Ck-1，
所以，
C 的不下降排列数就是 I-K 的首项是 B 的不同划分数，
又因为：
可知当 A-1=B 时，方案数相同，其中 A 能从 2 取到（I div k），而 B∈[1，(I-k) div k]
即 B∈[1,(I div k)-1], 所以，当 A∈[2，I div k]时，方案总数是 F（I-K，K）。又因为当
A=1 时，方案数是 F（I-1，K-1），所以：
F（I，K）=F（I-K，K）+F（I-1，K-1）成立。
由此我们也可以推出与上面第三个程序一样的状态转移方程。
浙公网安备 33021202002483