1. Greedy

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

2. 贪心算法与回溯和动态规划

贪心算法与动态规划的不同点：

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。

动态规划则会保存以前的运算结果，并根据以前的结果对当前进行 选择，有回退功能。

    贪心：当下做局部最优判断，同时是不能回退的；

    回溯：能够回退；

   动态规划：最优判断 + 回退；（带有最优判断的回溯就是动态规划）

3. 适用情景

    简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终 问题的最优解。这种子问题最优解称为最优子结构。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择， 不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前 进行选择，有回退功能。

     贪心法可以解决一些最优化问题，选最优选最近选最好都可以用贪心算法，如：求图中的最小生成树、求哈夫曼编码 等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案（选择眼前最优，一般来说达不到全局最优）。

     一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最 好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心 法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

4. 案例

Coin Change 使用贪心算法的特例

当硬币可选集合固定：Coins = [20, 10, 5, 1]

　　求最少可以几个硬币拼出总数。 比如 total = 36

      首先用20去匹配（36/20 整数个20）36 – 20 = 16， 再用6去匹配（16 / 10 整数个10）16 – 10 = 6， 再用5匹配，最后用1匹配得到 36.

这种特殊情况是，前面这些硬币依次是后面这些硬币的倍数（这些硬币20，10, 5， 1有整除关系），可以从数学上证明贪心法每次用最大的即可。这种特殊情况下，贪心算法是成立的。

Coin Change使用贪心算法的反例

非整除关系的硬币，可选集合：Coins = [10, 9, 1] 

　　求拼出总数为 18 最少需要几个硬币 ？最优化的方案是两个9， 使用贪心算法的结果是10, 1, 1, 1, 1, 1, 1, 1, 1 ，其结果并不是最优的。

　　18 – 9 = 9；

　 　9 – 9 = 0；

算法-04 | 贪心算法

原文地址：https://www.cnblogs.com/shengyang17/p/13309244.html