附录2：贪心法

第四讲 贪心方法

1. 一般方法

在现实世界中，有这样一类问题：它有n个输入，而它的解就由这n个输入的某个子集组成，不过这个子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件；而把满足约束条件的子集称为该问题的可行解。显然，满足约束条件的子集可能不止一个，因此，一般来说可行解不是唯一的。为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值(极大或极小)的可行解，称为最优解。这一类需求取最优解的问题，又可根据描述约束条件和目标函数的数学模型的特性或求解问题方法的不同，进一步划分为线性规划、整数规划、非线性规划、动态规划等问题。尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就是贪心方法（贪婪法）。

贪心方法是一种改进了的分级处理方法。它首先根据题意，选取一种量度标准。然后按这种量度标准对这n个输入排序，并按次序每次输入一个输入量。如果该输入和当前已构成在这种量度意义下的部分最优解组合在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法。要注意的是，对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的。但实际上，在贪心处理中，利用量度标准中的大多标准所得到的该量度意义下的最优解往往不是问题的最优解，而是次优解。尤其值得指出的是，把目标函数作为量度标准所得到的解也不一定是问题的最优解。因此，选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。在一般情况下，要选出最优量度标准并不是一件容易的事，不过，一旦能选择出某个问题的最优量度标准，那么用贪心方法求解这个问题则特别有效。

贪心方法可以用下面的抽象化控制来描述。

算法1.1 贪心方法的抽象化控制

void Greedy(a[]，n) {

贪心算法理解贪心算法的基本原理和应用场景

贪心算法：理解贪心算法的基本原理和应用场景

简介：

贪心算法（Greedy Algorithm）是一种常用的算法设计和解决问题的方法。它以一种贪婪的方式做出每一步的选择，希望最终能够达到整体上的最优解。本文将介绍贪心算法的基本原理和常见应用场景。

一、贪心算法的基本原理

贪心算法的基本原理是每次都做出当前最优的选择，希望最终能够达到整体上的最优解。贪心算法的优点在于简单、高效，但由于它只关注当前最优解，因此可能无法得到全局最优解。

贪心算法的基本步骤如下：

1. 将问题划分为若干子问题，每个子问题都有多个选择；

2. 分析子问题的选择，以及每个选择的最优解；

3. 根据每个子问题的最优解，做出当前最优的选择；

4. 更新已做出选择的子问题集合；

5. 重复步骤3和4，直到解决全部子问题。

二、贪心算法的应用场景 1. 零钱兑换问题

零钱兑换问题是指给定一个金额和一组零钱的面值，如何用最少数量的零钱找零。贪心算法可以从面值最大的零钱开始，每次找零选择当前面值最大的零钱，直到达到目标金额。

2. 区间调度问题

区间调度问题是指给定一组区间，如何选择最多数量的不相交区间。贪心算法可以根据区间的结束时间进行排序，每次选择结束时间最早的区间，并排除与之重叠的其他区间。

3. 背包问题

背包问题是指给定一组物品和一个固定容量的背包，如何选择物品放入背包，使得背包中物品的总价值最大。贪心算法可以通过计算每个物品的单位价值（即物品的价值与重量的比值）来选择单位价值最高的物品放入背包。

4. 最短路径问题

最短路径问题是指在一个有向图或无向图中，找到两个节点之间的最短路径。贪心算法可以使用Dijkstra算法，每次选择离起始节点最近的未访问节点进行扩展，直到找到目标节点。

5. 活动选择问题 活动选择问题是指在一组活动中，选出最大的互相兼容的活动子集合。贪心算法可以根据活动的结束时间进行排序，每次选择结束时间最早的活动，并排除与之重叠的其他活动。

1

穷举法、贪心法、分枝限界法

讲解人：

一、穷举法（枚举法）

（一）算法思路

就是从可能的解的集合中一一枚举各元素，用题目给定的检验条件，判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。

（二）例子（第二章介绍过的货郎担问题）

假定以编号为1的城市为始发城市，那么就会有4！=24个不同的路线，我们只要列举出每一条路线并分别计算出相应的费用即可。从中就可以找出最小费用及对应的路线。

（三）算法复杂度：O(n!)

（四）算法评价

优点：可得到精确值。当n较小时，是可行的；

缺点：较笨拙，由于须列举所有情况，且记录下每次的情况，需要大量的机时和内存空间。当n较大时，该算法是不可行性的。

二、贪心法

贪心法是一种对某些求最优解问题的更简单、更迅速的设计方法。

（一）引言

在给出贪心法的具体定义和算法步骤之前，我们先来看两个例子。

例1 假设有4种硬币，它们的面值分别为1角、5分、2分和1分。现要找给某顾客3角7分钱，这时，我们几乎不假思索地拿出3个l角、1个5分和1个2分的硬币交给顾客。我们不仅能很快决定要拿哪些硬币，而且与其它找法相比．我们拿出的硬币的个数肯定是最少的。

在这里，我们实际使用了这样的算法：首先选出一个面值不超过3角7分的最大硬币(1角)，然后从3角7分中减去1角，剩下2角7分再选出一个不超过2角7分的最大硬币(另一个1角)，如此做下去，直到找足3角7分。

例2 如图1—1，其中，顶点可解释为城市，边上的代价可解释为两城市问的里程。在图中找一条经过所有结点一次的回路，并使里程的总和为最小。这同样还是货郎担问题。在解此题时，我们可以按这样一个想法去做：

首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点：

1)不会有三条边(候选边及已入选边)与同一顶点相关联。

2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。

第三讲 贪心法

1. 贪心法的基本思想

贪心法是从问题的某一个初始解出发,向给定的目标推进。但不同的是,推进的每一步不是依据某一固定的递推式，而是做出一个在当前看来是最佳的贪心选择,不断地将问题实例归纳为更小的相似的子问题,并期望通过所做的局部最优选择产生出一个全局最优解。

2. 使用贪心法求解问题时要具备的条件

(1)所求解的问题应当具有贪心选择性质。即所求解的问题的整体最优解可以通过一系列的局部最优解得到。所以局部最优解是指在当前的状态下做出的最好选择。

(2)所求解的问题应当具有最优子结构性质。当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构。

3. 使用贪心法的注意事项

(1)要判断一个问题是否可以通过贪心算法得到最优解，是一件比较困难的的事情。这需要比较复杂而严格的数学证明。

(2)贪心算法不是对所有问题都能得到整体的最优解，但是实际应用中的许多问题都可以使用贪心算算得到最优解。

(3)即使使用贪心算法不能得到问题的最优解，但是最终结果也是最优解的很好的近似解。因此，在解决一般性问题时，使用贪心算法是一种不错的选择。

4. 贪心法的优点与不足

优点：算法思想简单，易于实现，效率高。

不足：使用贪心算法之前必须对问题本身进行深入而透彻地分析和证明，以保证使用贪心法得到最优解，而对问题进行分析与证明是比较困难的。

5. 贪心法在经典算法中的体现

(1)哈夫曼(Huffman)编码问题：编码最短

(2)求解最小生成树的克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法：代价最小

(3)求解图的最短路径的迪克斯特拉(Dijkstra)算法：路径最短

6. 举例

例1：找零钱问题。假设有3种硬币，面值分别为1元、五角、1角。这3种硬币各自的数量不限，现在要找给顾客2元7角钱，请问怎样找钱才能使得找给顾客的硬币数量最少呢？

分析：为了找给顾客的硬币数量最少，在选择硬币的面值时，当然是尽可地选择面值大的硬币。因此要找给顾客2元7角钱，且使得硬币数量最少，应该按照以下步骤：