算法导论-贪心

贪心算法

贪心算法通常是自顶向下设计的。也需要具有最优子结构。贪心算法也是一种启发式算法，并不能一定保证是最优解。

从动态规划到贪心算法的转化中，我们通常经理如下步骤：

1. 确定问题的最优子结构
2. 设计一个递归算法，可以用动态规划做
3. 证明如果做出一个贪心选择，则只剩一个子问题
4. 证明贪心选择总是安全的（3，4可以交换顺序）
5. 设计一个递归的贪心算法
6. 将递归贪心算法通过尾递归改成迭代算法

简化来看，我们可以根据以下步骤来设计贪心算法：

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

对于每一个贪心算法，都有一个更加繁琐的DP算法。关于如何证明贪心算法是最优算法，没有适用于所有情况的方法，但贪心选择性质和最优子结构是两个关键因素。

拟阵