概述

贪心法，又称贪心算法、贪婪算法:在对问题求解
时，总是做出在当前看来是最好的选择。

举个例子：

现在有4种纸币，20元，10元，5元，1元。请问现在要凑出36元的纸币，最少需要多少张纸币？

贪心算法解决如下：

首先拿出面值最大的20，此时还剩16。面值小于16最大的是10，再拿出一张10，此时面值还剩6。面值小于6最大的是5，再拿出一张5，此时还剩1，最后拿出1，共需要4张纸币。

缺点

贪心算法考虑的是目前最优的情况，着眼局部就会导致许多问题。

举个例子：

现在有3种纸币，10元，9元，1元。请问现在要凑出18元的纸币，最少需要多少张纸币？

如果按贪心算法解决：

首先拿出面值最大的10，此时还剩8。面值小于8最大的是1，再拿出8张1。共需要9张纸币。

实际只需要2张9元的货币就足够了。

贪心算法的适用场景

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

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

实现框架

从问题的某一初始解出发：
while (朝给定总目标前进一步)
{
利用可行的决策，求出可行解的一个解元素。
}
由所有解元素组合成问题的一个可行解；