释义

在设计算法求解最优化问题的过程中，每一步都做出当时看起来最佳的选择，这样的算法称作贪心算法，每一步做出的选择称作贪心选择。

设计步骤

1. 将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个待求解的子问题。
2. 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
3. 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

应用示例

活动选择问题

问题描述

假定有一个 n 个活动的集合 S={a1,a2,...,an}，这些活动使用同一个资源，而这个资源在某个时刻只能供一个活动使用。每个活动 ai 都有一个开始时间 si 和结束时间 fi，其中 0<=si<fi<∞。如果被选中，活动 ai 发生在 [si, fi) 期间。如果两个活动不重叠，则称他们是兼容的。在活动选择问题中，我们的目标是从 S 中选择一个最大兼容活动集。假定活动已按结束时间递增排序：f1<=f2<=f3<=...<=fn-1<=fn(16.1)。

设计步骤

贪心选择：
如何做出贪心选择呢？想要得到 S 的最大兼容活动集，也就是说：尽可能多的挑选 S 中时间不重叠的活动。需要在每一次的选择中，选择尽可能早结束的活动。因为这样以来，就留出更多的时间供之后的活动选择，更多的时间意味着可以选择更多不重叠的活动。

步骤如下：

1. 假定 Sk 为在 ak 结束后开始的活动集合，在第一次选择 a1 后，只剩下一个待求解的子问题 S1（Sk既可表示ak结束后开始的活动集合，也可表示一个子问题，需要结合上下文进行理解）。由于活动按照结束时间递增排序，所以 a1 一定是当前最早结束的活动，为贪心选择。而 S1 中都是 a1结束之后的活动，所以只需在下一次的选择中选择 S1 中最早结束的活动即为贪心选择。这样以来，每次都能做出贪心选择，且只剩下一个待解决的子问题。
2. 在此方案中每次做出贪心选择后，能保证之前的活动已经没有更优的，而之后的活动则包含在选择后产生的子问题中。因此，按照此方案进行贪心选择，原问题总是存在最优解，贪心选择总是安全的。
3. 由2的论述可以发现：某次选择 ak 后，所做的选择加上之前做的选择总能保证原问题存在最优解，因此 ak 及之前做出的选择的活动集合并上 ak 结束后的集合 Sk 的最优解能得出原问题的最优解。
   根据贪心选择，可以很容易得出如下递归算法：

/**
输入
s: 活动开始时间序列
f: 活动结束时间序列
k: Sk的下标k
n: 活动的数量
注意：为了方便，加入一个活动a0，f0=0，
这样以来，S0即表示原问题（所有活动的集合） 

输出
Sk的最大互相兼容的活动集合 
*/
recursiveActivitySelector(s, f, k, n)
    m = k+1
    while m<=n and s[m]<f[k]
        m = m+1
    if m<=n
        return {a[m]} U recursiveActivitySelector(s, f, m, n)
    else return null

以下为recursiveActivitySelector的一个迭代版本：

/**
输入
s: 活动开始时间序列
f: 活动结束时间序列

输出
Sk的最大互相兼容的活动集合 
*/
greedyActivitySelector(s, f)
    n = s.length
    A = {a1}
    k = 1
    for m=2 to n
        if s[m]>=f[k]
            A = A U {am}
            k = m
    return A