求解最优化问题要经过一系列步骤，每个步骤中有多种选择，有时使用动态规划来求解会十分复杂，此时可以使用更高效更简单的算法，如贪心算法。
贪心算法总是在每一步做出局部最优的选择，寄希望与这样的选择能够达到全局最优解。
贪心算法并不能保证得到最优解，但部分问题使用贪心策略足以达到最优解。
1. 活动选择问题
我们的第一个例子是一个调度竞争共享资源的多个活动的问题，目标是选出一个最大的，互相兼容的活动集合。
假定有一个n个活动的集合,这些活动使用同一个资源，而这些资源在某个时刻只能供一个活动使用。每个活动
都有开始时间
和结束时间
，如果被选中，任务占据该资源
期间。如果两个活动的区间不重叠，则称他们是兼容的。在活动选择问题中，我们希望选择出一个最大兼容活动集。
我们可以通过动态规划算法将这个问题分解为两个子问题，然后将两个子问题的最优解合并为原问题的解。
活动选择问题的最优子结构
令表示在
结束之后开始，且在
开始之前结束的那些活动集合。我们希望求
的最大兼容子集。进一步，我们假定
就是这样一个子集，且包含活动k。如此我们便得到两个子问题，寻找
中的兼容活动以及寻找
中的兼容活动。即我们可得到
我们用表示集合
的大小，则可得到
贪心选择
事实上，对于活动选择问题，我们无需考虑所有子选择，只需要考虑一个选择:贪心选择
对于活动选择问题，如何贪心选择？直觉上，我们应该选择这样一个活动，选出它后剩下的资源应该被尽可能多的其他任务利用。现在考虑可选的活动，其中必然有一个最先结束，我们应该选择S中最早结束的活动，因为剩下的资源可供他之后尽可能多的活动使用。
现在的问题是，我们的策略是正确的吗？下面的定理证明了这一点。
考虑任意非空子问题
，令
是
证明
令是
中的一个最大兼容活动子集，且
是
中结束时间最早的活动。若
,则已证明
在
的最大兼容活动子集中。否则,令集合
中的活动都是不相交的，而
结束更早，因此得出
也是Sk的一个最大兼容活动子集，且包含
由此得到代码如下
2.贪心算法原理
本节探究贪心算法的一般性质。
在上一节设计贪心算法的过程比通常繁琐一些，我们当时经过了如下步骤：
- 设计问题的最优子结构
- 设计一个递归算法
- 证明如果我们做出了贪心选择，则只剩下一个子问题。
- 证明贪心算法是有效的。
- 设计算法实现贪心策略。
一般的，我们可以根据如下步骤设计贪心算法：
- 将最优化问题转化为:对其做出一次选择后，只剩下一个子问题需要求解
- 证明做出贪心选择后，原问题总是存在最优解。
- 证明做出贪心选择后，剩余的子问题满足性质:即最优解与贪心选择组合即可得到原问题的最优解。
问题的关键在于贪心选择性质和最优子结构
贪心选择性质
当进行选择时，我们直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。
我们必须证明每个步骤做出贪心选择能生成全局最优解，这种证明通常首先考察某个子问题的最优解，然后用贪心选择替换某个其他选择来修改此解，从而得到一个相似但更小的子问题。
