目录

概述

贪心法的设计思想

贪心法概述

例子：用贪心法求解付款问题

贪心法的设计思想

贪心法求解的问题特征

贪心选择性质证明

贪心法设计的关键

与动态规划方法的比较

贪心法的求解过程

有关概念

贪心法的算法设计模式      

图问题中的贪心法

TSP第一种贪心选择策略

问题分析

算法设计

算法分析

最近邻点贪心策略正确性分析

TSP第二种贪心选择策略

算法设计

算法分析

最短链接贪心策略正确性分析

图着色问题

问题描述

问题分析

算法设计

算法分析

最小生成树问题

问题描述

问题分析—贪心策略1

算法设计

问题分析—贪心策略2

算法设计

组合问题中的贪心法

背包问题

问题描述

问题分析

算法设计

算法分析

算法的证明

背包问题与0/1背包问题

活动安排问题

问题描述

多机调度问题

问题描述

问题分析

算法设计

算法分析

---

概述

• 贪心法的设计思想

• 贪心法概述

贪心法在解决问题的策略上一般只根据当前已有的信息就做出选择，而且一旦做出了选择，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。

这种局部最优选择并不总能获得整体最优解（Optimal Solution），但通常能获得近似最优解（Near-Optimal Solution）。如果一个问题的最优解只能用蛮力法穷举得到，则贪心法不失为寻找问题近似最优解的一个较好办法。

• 例子：用贪心法求解付款问题

假设有面值3元、1元、8角、5角、1角的货币若干枚，需要找给顾客4元6角现金，为使付出的货币的数量最少，如何找零？  

首先选出1张面值不超过4元6角的最大面值的货币，即3元，再选出1张面值不超过1元6角的最大面值的货币，即1元，再选出1张面值不超过6角的最大面值的货币，即5角，再选出1张面值不超过1角的最大面值的货币，即1角，总共付出4张货币。

贪心解：4元6角= 3元+1元+5角+1角

方法：每一步的贪心选择策略：在不超过应付款金额条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且选择也不能改变，付款问题的贪心选择策略是尽可能使付出的货币最快的满足支付要求，其目的是使付出的货币张数最慢地增加。

最优解：4元6角=3元+8角+8角

需要3张货币：1个3元和2个8角。

• 贪心法的设计思想

使用贪心选择策略，把一个复杂的问题，分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。贪心法用于求解最优化问题。

• 贪心法求解的问题特征

（1）最优子结构性质

   当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。

（2）贪心选择性质

   所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即通过贪心选择得到。

• 贪心选择性质证明

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。

通常先考察问题的一个整体最优解，并证明可修改这个最优解，使其从贪心选择开始。做出贪心选择后，原问题简化为规模较小的类似子问题，然后，用数学归纳法证明，通过每一步的贪心选择，最终可得到问题的整体最优解。

• 贪心法设计的关键

能获得问题最优解的贪心选择策略

• 与动态规划方法的比较

共同点：需要最优子结构性质—最优性原理，都是求最优化问题。

不同点：

动态规划：每一步做一个选择—依赖于子问题的解。

贪心方法：每一步做一个选择—不依赖于子问题的解。

在动态规划法中，每步所做出的选择（决策）往往依赖于相关子问题的解，因而只有在求出相关子问题的解后，才能做出选择。而贪心法仅在当前状态下做出最好选择，即局部最优选择，然后再去求解做出这个选择后产生的相应子问题的解。即：贪心算法先做在当时看起来是最优的选择，然后再求解子问题，而不是先寻找子问题的解，然后再选择。

动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择，每做一次贪心选择就将问题简化为规模更小的子问题。

动态规划方法可用的条件

最优子结构性质

子问题重叠性

子问题空间小

Greedy方法可用的条件

最优子结构性质

贪心选择性质

可用Greedy方法时，动态规划方法可能不适用

可用动态规划方法时，Greedy方法可能不适用

 

• 贪心法的求解过程

• 有关概念

（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。

（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。

（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。

（4）选择函数select：即贪心选择策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心选择策略就是在候选集合中选择面值最大的货币。

（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。  

• 贪心法的算法设计模式      

 

图问题中的贪心法

• TSP第一种贪心选择策略

• 问题分析

求解TSP问题至少有两种贪心策略是合理的：

（1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。   

• 算法设计

设图G有n个顶点，边上的代价存储在二维数组w[n][n]中，集合V存储图的顶点，集合P存储经过的边，最近邻点策略求解TSP问题的算法如下：

• 算法分析

算法的时间性能为O(n^2)，因为共进行n-1次贪心选择，每一次选择都需要查找满足贪心条件的最短边。

• 最近邻点贪心策略正确性分析

通过实例分析，图中从城市1出发的最优解是1→2→5→4→3→1，总代价只有13。用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。

当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解。不过，这个近似解以何种程度近似于最优解，却难以保证。例如，在图中，如果增大边(2, 1)的代价，则总代价只好随之增加，没有选择的余地。

 

• TSP第二种贪心选择策略

（2）最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。因此，当从剩余边集E'中选择一条边(u, v)加入解集合S中，应满足以下条件：

① 边(u, v)是边集E'中代价最小的边；

② 边(u, v)加入解集合S后，S中不产生回路；

③ 边(u, v) 加入解集合S后，S中不产生分枝（就是没有节点度数超过3）；

• 算法设计

设图G有n个顶点，边上的代价存储在二维数组w[n][n]中，集合E'是候选集合即存储所有未选取的边，集合P存储经过的边，最短链接策略求解TSP问题的算法如下：

• 算法分析

在算法7.2.2中，如果操作“在E’中选取最短边(u, v)”用顺序查找，则算法7.2.2的时间性能是O(n^2)，如果采用堆排序的方法将集合E'中的边建立堆，则选取最短边的操作可以是O(log2n)，对于两个顶点是否连通以及是否会产生分枝，可以用并查集的操作将其时间性能提高到O(n)，此时算法7.2.2的时间性能为O(nlog2n)。

• 最短链接贪心策略正确性分析

通过实例分析，图中从城市1出发的最优解是1→2→5→4→3→1，总代价只有13。

用最短链接贪心策略求解TSP问题所得的结果不一定是最优解。

 

• 图着色问题

• 问题描述

给定无向连通图G=(V, E)，求图G的最小色数k，使得用k种颜色对G中的顶点着色，可使任意两个相邻顶点着色不同。

若一个图最少需要k种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数k为该图的色数。

若图G是平面图,则它的色数不超过4色(4色定理)。

4色定理的应用:在一个平面或球面上的任何地图能够只用4种颜色着色，使得相邻的国家在地图上着有不同颜色

例如，如下图所示的图可以只用两种颜色着色，将顶点1、3和4着成一种颜色，将顶点2和顶点5着成另外一种颜色。

为简单起见，下面假定k个颜色的集合为{颜色1, 颜色2, …, 颜色k}。

• 问题分析

贪心策略：选择一种颜色，以一个顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推。

考虑顶点顺序为1,2,3,4,5得到最优解

考虑顶点顺序为1,5,2,3,4得到近似解

用此贪心策略求解图着色问题所得的结果不一定是最优解。

• 算法设计

设数组color[n]表示顶点的着色情况，贪心法求解图着色问题的算法如下：

• 算法分析

本算法需要试探k种颜色，每种颜色，需要对所有顶点进行冲突测试，假设无向图有n个顶点，算法的时间复杂性是O(k*n)。

 

• 最小生成树问题

• 问题描述

设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树（Minimal Spanning Trees）。

• 问题分析—贪心策略1

最小生成树问题至少有两种合理的贪心策略：

（1）最近顶点策略：任选一个顶点，并以此建立起生成树，每一步的贪心选择是简单地把不在生成树中的最近顶点添加到生成树中。

普里姆算法（Prim算法）就应用了这个贪心策略,它使生成树以一种自然的方式生长，即从任意顶点开始，每一步为这棵树添加一个分枝，直到生成树中包含全部顶点。  

• 算法设计

设图G中顶点的编号为0～n-1

设连通网中有n个顶点，则第一个进行初始化的循环语句需要执行n-1次，第二个循环共执行n-1次，内嵌两个循环，其一是在长度为n的数组中求最小值，需要执行n-1次，其二是调整辅助数组，需要执行n-1次，所以，Prim算法的时间复杂度为O(n^2)。

• 问题分析—贪心策略2

(2）最短边策略：

设G=(V，E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选取最短边(u, v)，如果边(u, v)加入集合TE中不产生回路，则将边(u, v)加入边集TE中，并将它在集合E中删去。

克鲁斯卡尔算法（Kruskal算法）就应用了这个贪心策略，它使生成树以一种随意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，到最后合并成一棵树。

• 算法设计

Kruskal算法为了提高每次贪心选择时查找最短边的效率，可以先将图G中的边按代价从小到大排序，则这个操作的时间复杂度为O(elog2e)，其中e为无向连通网中边的个数。对于两个顶点是否属于同一个连通分量，可以用并查集的操作将其时间性能提高到O(n)，所以，Kruskal算法的时间性能是O(elog2e)。

 

组合问题中的贪心法

• 背包问题

• 问题描述

给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?     

设xi表示物品i装入背包的量，根据要求，有如下约束条件和目标函数：

于是，背包问题归结为寻找一个满足约束条件式7.1，并使目标函数式7.2达到最大的解向量X=(x1, x2, …, xn)。

• 问题分析

至少有三种看似合理的贪心策略：

（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。

（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。

（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。

应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。

• 算法设计

设背包容量为C，共有n个物品，物品重量存放在数组w[n]中，价值存放在数组v[n]中，问题的解存放在数组x[n]中。

该算法的解的形式为（1，….1,xk，0，…0），其中xk∈[0，1]，k∈ [1，n] 。由以上过程可知，选取最优的贪心选择策略为用贪心方法求解问题的核心。

• 算法分析

算法7.3.1的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此，其时间复杂性为O(nlog2n)。

• 算法的证明

证明的基本思想是：把这贪心解与任一最优解相比较，如果这两个解不同，就寻找开始不同的第一个xi，然后设法用贪心解的这个xi去代换最优解的那个yi，并证明最优解在分量代换前后的总价值无任何变化。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解是最优解。

讨论：

若σ>0时，则Y不是最优解，此与假设矛盾，所以不可能，即σ =0。

当σ=0时，则Z=X或Z≠X，则

若Z=X，则∑vizi= ∑viyi，由于Y是最优解，因此Z也是最优解，X也是最优解。

若Z≠X，重复上面的讨论，用Z代替Y，则又可求得相应的σ’ ≥ 0，重复以上过程，直到X=Z为止，可得X为最优解。

• 背包问题与0/1背包问题

若背包问题中的物体不能分拆,只能整个装入，则称为0-1背包问题.用贪心算法能得到0-1背包的最优解吗?

例：

n=3, C=25, (v1, v2, v3)=(35, 24, 15), (w1,w2,w3)=(18, 15, 10)

分析: 单位价值 (v1/w1, v2/w2, v3/w3)

          = (35/18, 24/15, 15/10)

          = (1.94, 1.6, 1.5)

          装入顺序: (x1,  x2,  x3)

          贪心解:(1, 0, 0), 总价值 35

          最优解:(0, 1, 1), 总价值 39

0-1背包问题和背包问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。

实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。

 

• 活动安排问题

• 问题描述

设有n个活动的集合E={1, 2, …, n}，其中每个活动都要求使用同一资源（如演讲会场），而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题要求在所给的活动集合中选出最大的相容活动子集。       

贪心法求解活动安排问题的关键是如何选择贪心策略，使得按照一定的顺序选择相容活动，并能安排尽量多的活动。至少有两种看似合理的贪心策略：

  （1）最早开始时间：这样可以增大资源的利用率。

  （2）最早结束时间：这样可以使下一个活动尽早开始。

由于活动占用资源的时间没有限制，因此，后一种贪心选择更为合理。

为了在每一次贪心选择时快速查找具有最早结束时间的相容活动，先把n个活动按结束时间非减序排列。这样，贪心选择时取当前活动集合中结束时间最早的活动就归结为取当前活动集合中排在最前面的活动。

例如，设有11个活动等待安排，这些活动按结束时间的非减序排列如下：

设有n个活动等待安排，这些活动的开始时间和结束时间分别存放在数组s[n]和f[n]中，集合B存放问题的解，即选定的活动集合，算法如下：

算法7.7的时间主要消耗在将各个活动按结束时间从小到大排序。因此，算法的时间复杂性为O(nlog2n)。

 

• 多机调度问题

• 问题描述

设有n个独立的作业{1, 2, …, n}，由m台相同的机器{M1, M2, …, Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

• 问题分析

多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。

约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。

贪心法求解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。

按照最长处理时间作业优先的贪心策略，当m≥n时，只要将机器i的[0, ti)时间区间分配给作业i即可；当m＜n时，首先将n个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。

例：设7个独立作业{1, 2, 3, 4, 5, 6, 7}由3台机器{M1, M2, M3}加工处理，各作业所需的处理时间分别为{2, 14, 4, 16, 6, 5, 3}。贪心法产生的作业调度如下：

• 算法设计

• 算法分析

在算法7.3.3中，操作“数组d[m]中最小值对应的下标”如果采用蛮力法查找，则算法的时间性能为：

通常情况下m<<n，则算法7.3.3的时间复杂性为O(n×m)。