贪心算法详解

贪心算法通过做出一系列选择求出问题的最优解。在每个决策点，它做出当时看来最佳选择这种启发式策略并不保证总能找到最优解，但对有些问题确实有效，比如活动选择问题。

贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。

比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。

设计贪心算法的过程一般经过以下几步：

1. 确定问题最优子结构
2. 设计一个递归算法
3. 证明如果我们做出一个贪心选择，则只剩下一个子问题
4. 证明贪心选择总是安全的（3，4可换）
5. 设计一个递归的算法实现贪心策略
6. 将递归算法转换为迭代算法

我们如何证明一个贪心算法是否能求解一个最优问题？贪心选择性质和最优子结构是俩关键因素。如果我们能证明问题具有这些性质，就向贪心算法迈出重要一步。

我们可以通过贪心选择来改进最优子结构，使得选择后只留下一个子问题。一般得，我们可以通过如下步骤设计贪心算法：

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

贪心选择性质

第一个关键因素是贪心选择性(greedy-choice property)：我们可以通过做出局部最优（贪心）选择来构造全局最优解。即我们进行选择时，直接做出当前问题中看来最优解，而不考虑子问题的解。

什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一小部分问题拥有这个性质。

这是贪心算法与动态规划不同之处。动态规划中，每个步骤都要进行一次选择，但选择通常依赖于子问题的解。譬如0-1背包问题不能使用贪心策略而分数背包问题可以。

比如你面前放着 100 张人民币，你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。

然而，大部分问题都明显不具有贪心选择性质。比如打斗地主，对手出对儿三，按照贪心策略，你应该出尽可能小的牌刚好压制住对方，但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法，而得使用动态规划解决，参见前文 动态规划解决博弈问题。

最优子结构

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。

当应用于贪心算法时，我们通常使用更为直接的子结构。我们可以假定，通过对原问题应用贪心选择即可得到子问题。我们真正要做的全部工作就是论证：将子问题的最优解与贪心选择组合在一起就能生成原问题最优解。这种方法隐含地对子问题做了数学归纳法，证明每个步骤进行贪心选择会生成原问题的最优解。

例如在视频拼接问题中，将所有时间区间按开始时间递增排序，相同开始时间情况下按结束时间递减排序：

我们的贪心选择是任意非空子问题中结束时间最晚的。这样问题被划分为贪心选择和子问题。我们只需要证明贪心选择总是最优解的一部分。

证明：设是的一个最小覆盖子集，且是中结束最晚的。如果，已经证明在的某个最小覆盖子集中。如果,令集合。则，并且，所以也是的一个最小子覆盖，且它包含贪心选择