贪心算法

贪心算法 是一种在对问题求解时，总是做出在当前看来是最好的选择的算法。也就是说，它不从整体最优上加以考虑，而是只考虑局部最优解，希望通过一系列局部最优的选择来达到全局最优或者近似全局最优的结果。

例如：找零钱问题

假设你购买东西后收银员需要给你找零 16 元。如果有多种面额的货币（1元、5元、10元），有多少种找法？

[10 * 1] [5 * 1] [1 * 1]

[10 * 1] [6 * 1]

[5 * 3] [1 * 1]

[1 * 16]

。。。

最少张？

[10 * 1] [5 * 1] [1 * 1]

每次都优先选择面值最大的纸币，直到不能再选（因为再选就会超过给定金额），然后选择次大面值的纸币，以此类推。

小结

可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。

贪心是一种解题策略，也是一种解题思想。使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优。

利用贪心策略解题，需要重点解决两个问题

1) 该题是否适合于用贪心策略求解

2) 如何选择贪心标准，以得到问题的最优/较优解

局部最优 与 全局最优

在一个 n * n 的迷宫中，你只能向右或下行走。问：从左上角走到右下角能收集到的最大能量值？

贪心策略_局部最优

非贪心策略_全部最优

总结

贪心算法通常比较简单、直观，容易理解和实现。它的时间复杂度相对较低，在很多情况下能够快速地得到一个可行解。

虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题都能产生整体最优解或是问题的次优解。