贪心算法入门详解，经典实例分析

贪心算法的字面有本是形容人的“贪心”一词，着实有些引人注目，有人说贪心算法是世界上最简单的算法，原因很简单：所有人都很“贪心”，根本不用学，不过，算法会怎样贪心呢？

“贪心”的人，事事都想要得到眼前最好的那个，看不到长远的东西，也不为将来最终结果做打算，换句话说，就是走一步看一步，只期望当前局部的利益最大化。粗略来看，贪心算法也差不多，它总做出当前来看最好的选择，追求局部最优，并“期望”局部最优能够带来全局最优。

贪心算法真的很贪婪，每一步都想要最好的，最后还期望能够得到全局最优。

找零钱问题

说起贪心算法，就不得不提经典的找零钱问题：顾客光顾你的小店买东西付了钱，你需要找钱给他 41 分钱，抽屉里只有 25 分、10 分、5 分和 1 分四种硬币，怎样找钱才能达到使用最少硬币个数的目的？在开始求解前，我们先明确一下限制：

1. 抽屉里有 25 分、10 分、5 分和 1 分四种硬币
2. 需要搭配出 41 分钱
3. 使用的硬币个数要最少

从直觉上来看，要满足限制3，一开始就应该使用最大币值的硬币，这样一来，接下来要找的钱最少，更容易达成使用最少硬币个数的目的。贪心算法不会想那么多，既然眼前的直觉如此，那就这么干：

1. 首先，币值最大的是 25 分硬币，因此先找出一个 25 分硬币
2. 经过第一步，还需要找 16 分钱，符合条件的最大币值硬币为 10 分硬币
3. 经过前两步，还需要找 6 分钱，符合条件的最大币值硬币为 5 分硬币
4. 经过前三步，还需要找 1 分钱

因此，贪心算法给出的找钱策略为 41 = 25+10+5+1，仔细分析下，这样的策略也是最优解，可见，只考虑局部最优也是有可能带来全局最优的。而且这样的策略很简单，几乎不用动脑，跟随本能即可，对应的C语言代码也是极其简单的：

#include <stdio.h>

int main()
{
    int change = 41;
    int num_25 = 0, num_10 = 0, num_5 = 0, num_1 = 0;
    // 优先使用最大币值的硬币
    while (change>=25) {
        num_25 ++; change -= 25;
    }
    while (change>=10) {
        num_10 ++; change -= 10;
    }
    while (change>=5) {
        num_5 ++; change -= 5;
    }
    while (change>=1) {
        num_1 ++; change -= 1;
    }
    printf("num_25: %d, num_10: %d, num_5: %d, num_1: %d\n",
                num_25, num_10, num_5, num_1);
    return 0;
}

编译并执行上述C语言代码，输出如下：

num_25: 1, num_10: 1, num_5: 1, num_1: 1

应该注意的是，贪心算法并不一定总是能够得到全局最优解。还是以找零钱为例：假设抽屉里除了 25 分、10 分、5 分和 1 分四种硬币外，还有一种 20 分的硬币，依然需要以最小硬币数找出 41 分的零钱。不难考证，贪心算法给出的找钱策略依然是 41 = 25+10+5+1，需要 4 枚硬币，但这显然不是最优解，因为 41 = 20+20+1 的找钱策略仅需 3 枚硬币即可。

可见，贪心算法近乎依据本能的求解策略虽然简单、高效，省去了找最优解可能需要的穷举操作，但是由于它“鼠目寸光”，仅追求眼前的局部最优，常常不能得到全局最优解。

会议室使用效率问题

再来看一个例子：公司装修，只有一个会议室可用，但是每天都有很多例会，这些例会的起止时间分别为 s(i) 和 f(i)，如下表：

怎样安排，才能充分利用会议室呢？（也即能开更多例会？）

为了更加方便的讨论，我们先用数学语言描述该问题，即：有 n 个例会的集合 S={a1, a2, ..., an}，这些例会可以在同一个会议室进行，但是会议室在某时刻只能供一个会议使用，每个例会 a(i) 的起止时间为 s(i) 和 f(i)，显然 0≤s(i)<f(i)。如果两个例会 a(i) 和 a(j) 的时间段不冲突，也即 [s(i), f(i)) 和 [s(j), f(j)) 不重叠，也即 f(i)≤s(j) 或者 f(j)≤s(i)，则称它们是兼容的。我们期望会议室能够举行更多的例会，也即能够找到最大兼容例会集合。

根据上表，子集 {a3, a9, a11} 是兼容例会子集，但它不是一个最大子集，因为 {a1, a4, a8, a11} 更大。实际上，{a1, a4, a8, a11} 是一个最大兼容例会子集，另一个最大子集是 {a2, a4, a9, a11}。

对于更一般的问题，假设公司每天有 n 个例会（n不一定等于11，会议时间段也不一定如上表所示），要找到最大兼容例会子集合，显然可以使用本专栏第一节讨论的“动态规划”方法将问题拆分为两个子问题，然后再将两个子问题的最优解整合为原始问题的一个最优解。

在确定该将哪些子问题用于最优解时，要考虑几种选择，而贪心算法只需考虑一个选择（贪婪，只在乎眼前的局部最优），稍后将基于贪心策略找到最大兼容例会子集合。

在使用“贪心策略”之前，我们先基于动态规划的思想分析问题，这对于稍后讨论“贪心策略”有所帮助。

动态规划法

令 S(ij) 表示 a(i) 结束之后到 a(j) 开始之前之间的例会集合，假定 A(ij) 是 S(ij) 的一个最大兼容例会子集，包含例会 a(k)。显然，a(k) 将 s(ij) 分为两部分，如下图：

a(k) 将 s(ij) 分为两部分

而 A(ik) 则表示 A(ij) 中那些在 a(k) 开始之前结束的例会，A(kj) 表示 A(ij) 中那些在 a(k) 结束之后开始的例会，因此，显然有下面这样的公式：

A(ij) = A(ik)+a(k)+A(kj)

所以，对于集合 S(ij)，它的最大兼容子集 A(ij) 包含的例会数目如下：

|A(ij)| = |A(ik)| + 1 + |A(kj)|

这样刻画的最优子结构，意味着我们可以使用动态规划法求解最大兼容例会子集问题。令 c[i,j] 表示集合 S(ij) 最大兼容子集中例会的数目，则很容易得到递归式：

c[i,j] = c[i,k] + 1 + c[k,j]

上面的递归式是基于假设条件“A(ij) 包含例会 a(k)”推出的，事实上，如果要求解原始问题，我们需要遍历所有的 a(*)，以求得原始问题的最大兼容子集：

c[i,j] = max(c[i,k] + c[k,j] + 1), 其中要在S(ij)中遍历所有 a(k)

有了这样的数学表达式，相信看过本专栏第一节的读者都能轻易的使用自己熟悉的编程语言写出对应的算法代码。

使用动态规划法的确能够找到最优解，但是却需要考虑到所有的子问题，繁琐了些。贪心算法无需求解所有的子问题就可以选出最大兼容例会子集。

1 4 8 11

仔细分析下，不难发现 {a1, a4, a8, a11} 的确是一个最优解，至此，我们就使用贪心算法解决了会议室使用效率问题。与动态规划相比，贪心策略不需要遍历所有的子问题，仅需选择当前看起来最优的解即可，这使算法变得简单。不过应该注意，如果希望得到全局最优解，在使用贪心算法之前，应该有充分的证明当前的建模能够达成全局最优，所以也可以说，“贪心算法”表面上看起来简单，实际上并非如此，我们应该把贪心策略当作是一种设计算法的指导思想，而不是把“贪心算法”仅仅当作一种独立的算法，

贪心算法使用起来的确简单，似乎只需要跟着直觉走，无需再考虑遍历复杂的所有子问题，但是贪心算法这样随性的策略常常并不一定能够带来全局最优解。不过，贪心算法本质上是一种算法的设计思维，“使用贪心算法只能碰运气求全局最优解”，其实并非如此，通过本文后面的会议室使用效率问题，我们能够看出，算法的设计永远不是只能使用一种思维。在求解会议室效率问题时，我们虽然先基于动态规划思想做了分析，稍稍复杂了些，但最后还是能够结合贪心思想，设计出更加简洁的算法。

事实上，贪心策略是一种强有力的策略，可以很好的解决很多问题，在以后的学习中，我们可能会遇到许多基于贪心策略设计的算法，例如最小生成树算法，单元最短路径的 Dijkstra 算法等等。