本文将和同学们一起讨论一个生活中常见的问题，找零钱问题。看似很普通的找零钱问题，实际上我们一直在使用贪心算法进行找零。我们先来模拟一个找零问题，然后从找零问题推导出问题的最优解，最后来认识贪心算法。

下面来模拟一个找零问题。现在假设有面值1角、2角、5角、10角（1元）的硬币各10枚，要求用最少的硬币数量来找零。例如：找1.3元的零钱，1.3元转换成角，就是13角。

找零钱就是把不同面值或同一面值的硬币组合起来，组合的面值等于需要找零的钱数。1.3元转换成角就是13角。
下面有A、B、C三种硬币的组合方法：A组合方法：1个10角的硬币、3个1角的硬币;B组合方法：1个10角的硬币、1个2角的硬币、1个1角的1币；C组合方法：2个5角硬币、1个2角硬币、1个1角硬币。

在上面的三种硬币面值组合中，A组合需要4个硬币、B组合需要3个硬币、C组合需要4个硬币。

显然，B组合是最优组合，也称为问题的最优解。虽然A、B、C三种组合都是问题的解，但只有B组合符合人们对问题解的要求。感兴趣的同学有时间时可以进行更多种的组合，看看还有没有最优解。

在前面的找零问题中，A、B、C三种硬币组合都是问题的解，都可以组合成1.3元的零钱，但符合人们要求的解只有B组合，B组合也称为问题的最优解。

问题的最优解

问题的最优解可以简单理解为符合人们预期或让人满意的问题解法。例如在找零问题中，人们的预期是用最少的硬币数找零，在A、B、C三种找零的解法中，B是符合预期的，因此B是最优解，A和C就不是最优解。

在同一问题的解法中，有时最优解可能不止一个。例如外出旅行时，希望旅行预算在5000以内，因此5000以内的预算方案都是最优解，在这里我们就不再讨论了。

问题的最优解是与人们预期相关的，人们对问题最满意的解法就是问题的最优解。举个容易理解的例子：在算数问题中，假设以算的快为人们满意的解法。那么，当求解从1开始一直加到10这个问题时，（1+10）*5的解法就是最优解，它显然要比1+2+3+4+5+6+7+9+10这么计算要快的多。

贪心算法
前面的找零问题中，B组合是最优解，用的硬币数量最少，其实在找零问题上，我们一直在使用一种算法，这种算法就是贪心算法。

对比前面的A、B、C三种组合，我们发现B组合在找零过程中，它首先选用面值最大的10角硬币1枚，由于5角硬币不满足组合要求（找零过程中硬币的组合面值不能大于找零的零钱数），它继续选用比5角硬币面值次之的2角硬币1枚（找零过程中硬币的组合面值不能大于找零的零钱数），最后选用比2角硬币面值次之的1角硬币1枚。

在A、B、C三种找零算法中，B找零算法是首先选择面值最大的硬币，然后再选择面值次之的硬币，依次类推直至硬币组合的面值等于零钱数。这种算法也称为贪心算法（也叫贪婪算法），贪心算法就是在解决问题的过程中，总是做出在当前看来是最好的选择，也就是在解决问题的每一个步骤中，都会找当前步骤的最优解。

在找零过程中，B组合就是首先用最大面值的硬币，再依次选用面值次之的硬币。例如使用贪心算法找5.6元的零钱的步骤如下：（1）选择10角硬币5枚，面值总额为50角；（2）选择5角硬币1枚，面值总额为55角；（3）选择1角硬币1枚，面值总额为56角。

在找零问题中应用贪心算法，我们总能很快找到找零的最优解，找零5.6元仅需要7枚硬币即可。使用其它算法不会优于贪心算法给出的最优解，最优解就是使用最少的硬币数量来找零。感兴趣的同学们可以试一试，看看能不能找到比使用贪心算法更好的最优解。

思考与练习
现在有一块长20米，宽2米的长方形草坪，需要在长方形草坪的横中心线上放置半径为r的喷水装置，每个喷水装置可以覆盖以喷水装置为圆心，r为半径的圆形区域。要求在给出不同半径的喷水装置中，选择最少的喷水装置覆盖整个长方形草坪，并且已放置喷水装置的覆盖范围，尽量不要超过长方形草坪的长度区域。

半径为2米的喷水装置有20个，半径为2.5米的装置有10个，半径为4.5米的有6个。