贪心算法

贪心算法 ： 在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法（也就是说，结果不一定是最优解）。

经典例子——找换硬币问题

考虑用最少的硬币数 来找 n 分钱的问题，假设每个硬币的值都是整数。

这里的贪心策略很容易想到：总是优先选择 大面值的硬币 去找。比如，现有 1分、5分、25分的硬币可用来找钱，现在我们需要找 n=32分 的零钱，如何找？

优先选择大面值的嘛，那就是先选 25分；选完之后，还要找32-25=7，那就再选5分的，最终再先2个1分的。即可。

算法实例

1. 哈夫曼编码
2. 最小生成树