贪心算法基础

贪心算法是以动态规划算法为基础的。在每一个贪心算法的下面，总是会有一个更加复杂的动态规划解。如何判断某个问题是否可以使用贪心算法呢？关键点就是验证其具有贪心选择性质：一个全局最优解可以通过局部最优选择来达到。真正要做的就是证明将子问题的最优解与所做的贪心选择合并后，的确可以得到原问题的一个最优解。

都知道动态规划算法是贪心算法的基础。那在想使用贪心算法的时候，是不是可以考虑先构造其动态规划算法，然后考虑将其转化为贪心算法。[贪心选择性质的证明并不是很容易，而且往往是证实容易，证伪难。如何证明，很大程度上跟如何选择有关系，如果能先表明这种选择的动态规划算法正确，再证明其贪心选择性质要容易]。下面是一个基本步骤：

1. 决定问题的最优子结构
2. 设计一个递归解；
3. 证明在递归的任一阶段总是贪心选择。
4. 证明通过做贪心选择，所有子问题（除一个以外）都为空
5. 设计出一个实现贪心策略的递归算法
6. 将递归算法转换为迭代算法

在《算法导论》中，提到的活动选择问题就是这样的一个好例子。不过其中最难想到的就是如果做贪心选择，并且证明其具有贪心选择性质。也就是定理16.1。

对于任意非空子问题S_ij，设a_m是S_ij中具有最早结束时间的活动

f_m = min｛f_k：a_k（- S_ij｝

那么

1. 活动a_m在S_ij的某最大兼容活动子集中被使用。

2. 子问题Sim为空，所以选择a_m将使子问题S_mj为唯一可能非空的子问题。

在活动选择问题中，选择一个活动a_k，假定它在最终的最优解中，随之产生的子问题是a_k之前和a_k之后的两个子问题。