释义
在设计算法求解最优化问题的过程中，每一步都做出当时看起来最佳的选择，这样的算法称作贪心算法，每一步做出的选择称作贪心选择。
设计步骤
- 将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个待求解的子问题。
- 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
- 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
应用示例
活动选择问题
问题描述
假定有一个 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 中时间不重叠的活动。需要在每一次的选择中，选择尽可能早结束的活动。因为这样以来，就留出更多的时间供之后的活动选择，更多的时间意味着可以选择更多不重叠的活动。
步骤如下：
- 假定 Sk 为在 ak 结束后开始的活动集合，在第一次选择 a1 后，只剩下一个待求解的子问题 S1（Sk既可表示ak结束后开始的活动集合，也可表示一个子问题，需要结合上下文进行理解）。由于活动按照结束时间递增排序，所以 a1 一定是当前最早结束的活动，为贪心选择。而 S1 中都是 a1结束之后的活动，所以只需在下一次的选择中选择 S1 中最早结束的活动即为贪心选择。这样以来，每次都能做出贪心选择，且只剩下一个待解决的子问题。
- 在此方案中每次做出贪心选择后，能保证之前的活动已经没有更优的，而之后的活动则包含在选择后产生的子问题中。因此，按照此方案进行贪心选择，原问题总是存在最优解，贪心选择总是安全的。
- 由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
