安徽芜湖一中江涛
1
贪心算法概论
贪心算法一般来说是解决“最优问题”，具有编程简单、运行效率高、空间
复杂度低等特点。是信息学竞赛中的一个有为武器，受到广大同学们的青睐。本
讲就贪心算法的特点作些概念上的总结。
一、贪心算法与简单枚举和动态规划的运行方式比较
贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有n个输入，
它的解是由这n个输入的某个子集组成，并且这个子集必须满足事先给定的条
件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这
些可行解可能有多个。为了衡量可行解的优劣，事先给了一个关于可行解的函数，
称为目标函数。目标函数最大（或最小）的可行解，称为最优解。
a)求“最优解”最原始的方法为搜索枚举方案法（一般为回溯法）。
除了极简单的问题，一般用深度优先搜索或宽度优先搜索。通常优化方法为利
用约束条件进行可行性判断剪枝；或利用目标函数下界（或上界），根据当前最
优解进行分枝定界。
b)其次现今竞赛中用的比较普遍的动态规划（需要满足阶段无后效性原则）。
动态规划主要是利用最最优子问题的确定性，从后向前（即从小规模向大规模）
得到当前最优策略，从而避免了重复的搜索。
举例说明：求多段图的最短路径。
在图（1）中，我们省略了各线段的长度。
1
2
3
4
5
6
7
8
9
10
11
图（1）
安徽芜湖一中江涛
2
如果用回溯法，搜索树大致如下：
显然，上面的搜索有大量重复性工作。比如节点8、9、10到11的最短路分别
被调用了9次，从节点5、6、7到节点11也分别搜索了3次。
如果先算出节点8、9、10到11的最短路，由于它与前面的点无关，因此最优
值确定下来，再用它们求定节点5、6、7到节点11的最短路径。同理，再用节
点5、6、7的最优值，来求节点2、3、4优值。最后从节点2、3、4推出1到
11的最优值。显然复杂度大为降低。
当然，如果本题把简单搜索改为搜索＋记忆化的方法，则就是得能动态规划的
原理，本质上就是动态规划，只是实现的方法不同与传统的表格操作法。搜索＋
记忆化算法有其特有的特点，以后再讨论。
c)贪心算法则不同，它不是建立在枚举方案的基础上的。它从前向后，根据当
前情况，“贪心地”决定出下一步，从而一步一步直接走下去，最终得到解。
假如上面的例子中，我们定下这样的贪心策略：节点号k%3==1。则有图3：
1
234
567567567
A89A89A89A89……………………………..
图（2）
11
安徽芜湖一中江涛
3
显然，它只访问了节点1、4、7、10、11，工作量最少，效率最高。当然，对
本题来说，它不能得到最优解―――最短路径。
从图3中可以看出，贪心算法是一种比动态规划更高效的算法。只是要保证得
到最优解是贪心算法的关键。
贪心算法的一般框架为：
ProcedureGreedy（A，n）//A问题有n个输入
Begin
Init(ans)//初始化
fori:=1tondo
now=select(A)//按设计的标准选取一个“节点”
delete(A,now)//把A中的now删掉
ifcan(ans,now)thenunio(ans,now)//如果可行性通过，放入解中。
endfor
end;
1
234
567567567
A89A89A89A89……………………………..
图（3）
11
安徽芜湖一中江涛
4
二、贪心算法的关键――――正确性证明
动态规划要满足最优子结构原则，贪心算法呢？就目前的资料看，有个证明
模型是“矩阵胚理论”，但要证明一个问题是矩阵胚，十分困难。并且也不常见
的可用贪心算法问题都能用矩阵胚来证明。因此，可以认为贪心算法的正确性证
明是个难点。因此有些选手在没能证明时，也大胆设想结论应该是正确的。有时
这难免会放错。
例如95年NOI中的“石子合并”一题：
例一、石子合并
试题：
在一个圆形操场的四周摆放N堆石子(N≤100)，现要将石子有次序地合并
成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，
记为该次合并的得分。
编一程序，由文件读入堆数N及每堆石子数(≤20)
选择一种合并石子的方案，使得做N-1次合并，得分的总
和最小；选择一种合并石子的方案，使得做N-1次合并，
得分的总和最大。
例如，图4所示的4堆石，每堆石子数（从最上面的
一堆数起，顺时针数）依次为4594。则3次合并得分总和
最小的方案为图5，得分总和最大的方案为图6。
图4
4
9
45
总得分=8+13+22=43
图5
4
9
45
8
9
5
9
13
22
总得分=14+18+22=54
图6
4
9
45
4
4
1418
4
22
安徽芜湖一中江涛
5
输入数据
文件名由键盘输入，该文件内容为：
第1行为石子堆数N；
第2行为每堆石子数，每两个数之间用一个空格符分隔。
输出数据
输出文件名为output.txt；
从第1至第N行为得分最小的合并方案。第N+1行是空行。从第N+2行
到第2N+1行是得分最大合并方案。
每种合并方案用N行表示，其中第i行(1≤i≤N)表示第i次合并前各堆石
子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相
应的负数表示，以便标识。
输入输出示例：
当时这题是第一次出现，几乎有半数以上人都选择了贪心算法―――每次选
相邻和最小的两堆石子合并。
其实由于只能是相邻的两堆石子合并，并不能套用经典的哈夫曼树算法。本
题给的样例数据实际上是一个“陷阱”，造成了用贪心法即可解决的假象。
当一个贪心算法不能确定其正确性时，在使用之前，应该努力去证明它的不
正确性。而要证明不正确性，一种最简单的形式就是举一个反例。本例的反例见
图7。
INPUT.TXTOUTPUT.TXT
4-459-4
4594-8-59
-13-9
22
4-5-94
4-14-4
-4-18
22
图7
5
2
4
43
6
贪心算法的最小值为：
(2＋3)=5
(4+5)=9
(4+5)=9
(9+6)=15
(15+9)=24
5＋9＋9＋15＋24＝62
另一种方法的最小值为：
(2＋4)=6
(3+4)=7
(5+6)=11
(7+6)=13
(11＋13)=24
6＋7＋11＋13+24＝61
安徽芜湖一中江涛
6
常见的证明方法：
贪心算法的正确性证明虽然不容易，但一些常见的方法还是值得总结的。
a)构造法
根据描述的算法，用贪心的策略，依次构造出一个解，可证明一定是
合法的解。即用贪心法找可行解。
b)反证法
用贪心的策略，依次构造出一个解S1。假设最优解S2不同与S1，可
以证明是矛盾的。从而S1就是最优解。
c)调整法
用贪心的策略，依次构造出一个解S1。假设最优解S2不同与S1，找
出不同之处，在不破坏最优性的前提下，逐步调整S2，最终使其变为S1。
从而S1也是最优解。
下面分别举例说明。
例2士兵排队问题（1996年中国队选拔赛）----构造法证明
试题：
有N个士兵(1≤N≤26)，编号依次为A，B，C，...。队列训练时，指挥官
要把一些士兵从高到矮依次排成一行，但现在指挥官不能直接获得每个人的身高
信息，只能获得“P1比P2高”这样的比较结果(P1，P2∈A，B，C，...，Z，记
为P1>P2)，如“A>B”表示A比B高。
请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。
注：比较结果中没有涉及到的士兵不参加排队
输入数据
比较结果从文本文件中读入(文件名由键盘输入)，每个比较结果在文本文
件中占一行。
输出要求
若输入数据无解，打印“NoAnswer！”信息，否则从高到矮依次输出每一
个士兵的编号，中间无分隔符，并把结果写入文本文件中，文件名由键盘输入。
输入输出示例
INPUT.TXT
A>B
B>D
F>D
OUTPUT.TXT
AFBD
安徽芜湖一中江涛
7
显然用每次选“偏序中最高士兵”的贪心算法就可构造出一个可行解。这个
问题转就是“拓扑排序”问题。可这样证明：如果有解，就一定无环，因此每步
贪心都一定能进行下去。
经典的“找欧拉回路”问题也类似。
例3排队问题----反证法证明
试题：
在一个超市，有N个人排队到一个柜台付款，已知每个人需要处理的时间为
Ti（0
输入数据
文本文件中第一行为一个正整数N≤10000，第二行有N个不超过1000的正
整数Ti。
输出要求
只一个正整数：大家排队时间的最小总和。
输入输出示例
本题的贪心算法为：N个数据从小到大排序，就是这N个人的最佳排序方案。
求部分和的和即可得到答案。
反证法证明如下：
假设有最优解序列S1,S2,S3….,Sn，如果S1不是最小的Tmin，不妨设
Sk=Tmin，将S1与Sk对调。显然对Sk之后的人没影响，对Sk之前的人等待时
间都减少了(S1-Sk)>0。从而新的序列比原最优解序列好，矛盾！
固S1为最小时间。
同理可证S2是第二小的数，……。
证毕。
下面的调整法也有类似的思想，只是侧重点在“这样调整不会差”。
例4切巧克力问题----调整法证明
试题
我们提供给你一块mn的巧克力（如图8所示），你需要将这块巧克力切割成11的单
位巧克力。
INPUT.TXT
4
51087
OUTPUT.TXT
67
安徽芜湖一中江涛
8
图8巧克力
具体来说，对于一块巧克力，你有两种切割的方法。一种是沿着某条竖线将巧克力切成
两块，另外一种自然是沿着某条横线将巧克力切成两块。切割需要一定的花费，费用的计算
与所切割的巧克力的大小没有关系，而只于沿着哪条线切割有关。我们将沿着横线切割的费
用定义为y1、y2、……、ym-1；同样的，将沿着竖线切割的费用定义为x1、x2、……、xn-1。
现在，需要你计算的就是，怎样切才能使总费用最少？
在图8中，如果我们先沿着横线将整块巧克力切成四块，然后对于每一小块，分别沿着
竖线切割，那么总共的费用就是4)(4321321′++++++xxxxyyy。
【输入格式】
输入文件chocolate.in的第一行包含两个整数)1000,1(,￡￡mnmn，表示巧克力的大
小。接下来的n-1行每行包含一个整数，分别表示沿竖线切割的费用（上图中x1，x2，……），
接下来的m-1行也是每行包含一个整数，表示沿横线切割的费用（上图中的y1，y2，……）
【输出格式】
输出文件chocolate.out应该包含一个整数，表示你得到的最小切割费用。
样例输入
64
2
1
3
1
4
4
1
2
样例输出
42
安徽芜湖一中江涛
9
分析：
不妨设，Xi已经从大到小排序；Yi也同样。
如果把问题简化，只有横的切Xi或只有竖的切Yi，则显然和排队问题是一样
的，可以用贪心算法。横、竖可以交错切呢？
对任意一种方案，只看其中横切的Xi序列，如果不是从大到小排列，找到第
一个违反有序原则的，设为Xp，找出应该在这个位置的――即后面不小于Xp
的Xq，把Xp与Xq对调，显然新方案会更好。如此，有
结论一：
任意最优方案在不改变竖切次序前提下，可调整成横切是有序的最优解。
同理，有
结论二：
任意最优方案在不改变横切次序前提下，可调整成竖切是有序的最优解。
综合结论一和结论二，有
结论三：
任意一种最优方案，可调整成横切、竖切都有序的最优解。
如此，可简单得到动态规划算法，时空复杂度约为O(106)。
上面虽然用了贪心算法的反证法解决了问题，但没有将贪心算法思想进行到
底。我们可以进一步用调整法和反证法的思想，将最优解调整到不分横切、竖切，
都是递减的。
简单证明如下：
设有最优方案序列XY[1..n+m]，序列中任意两相邻项XY[i]和XY[i+1]，记为
a和b，若a≤b，分三种情况考虑：
(1)若a、b同是横切，显然交换a、b不影响最优解；
(2)若a、b同是竖切，显然交换a、b也不影响最优解；
(3)a和b不同，最交换a、b后，增加费用a，减少费用为b，共增加费用为
(a-b)≤0，不会破坏最优性。
反复检查，最终调整为全部有序的最优解。
这样最终得到一个简单的算法：只要排序就可以了。
进一步，如果切过的巧克力可分别拿开，各自选方案切割。也可用调整法证明
上面的方案也是最优解。
安徽芜湖一中江涛
10
流水线调度问题
由于篇幅关系，后面的两节就简单列个提纲。
三、一些经典贪心算法问题
磁带最优存储
背包问题
有限期的作业排序
哈夫曼树
最小生成树---Prim算法
最小生成树---Kruskla算法
教室问题
四、贪心算法应用的多样性
（1）构造出次序
在众多的选择中，按预先设计的某种次序来确定当前要找的下一步选择。
单源最短路径：Dijkstra算法
最小生成树
（2）局部（阶段）正确
有时整个问题不能用贪心法，但我们确定了部分因素后，后面的方案就可以
用贪心算法了。即通常简称：枚举＋贪心
从汽车过沙漠到登山问题
（3）快速求得一“较好”可行解
前面提到的搜索枚举方案法中，要很多题都可通过贪心算法得到一个“较
优可行解”。有时甚至用“启发＋随机化”多次贪心，能得到一个很好的上界（或
下界）。
（4）快速分枝定界
安徽芜湖一中江涛
11
接上面话题，在搜索过程中，有时也可以用贪心算法预测已有方案以后可能
达到的最小值（或最大值），再用“当前最好解”进行分枝定界。
从原始背包问题到0/1背包
（5）对称性游戏
根据问题的特点，直接确定一步，保证次把必败状态留给对方。
圆桌放硬币游戏
取数游戏
|
|
