测试常见算法面试题：贪心法--找零问题

贪心算法（Greedy Algorithm）摘要

贪心算法是一种在每一步选择中都采取当前状态下最优的选择，以期达到全局最优解的算法。它适用于通过一系列局部最优选择可以得到全局最优解的问题，并在面试中常见，如找零问题。

找零钱问题示例

以找零钱问题为例，如果需要找零36元，而手头有1元、5元、10元、20元和50元的硬币，贪心算法会优先选择最大面额的硬币。根据算法，首先选用一枚20元硬币，然后是10元、5元和1元，共使用四枚硬币完成找零。

该算法的局部最优解是每次挑选面值最大的硬币，直至解决问题。虽然简单有效，但贪心算法可能并不适用于所有问题，因为并非所有问题的全局最优解都可以通过贪心选择得到。

Python代码实现

使用Python语言实现的贪心算法可以计算出最小硬币数量。代码首先将硬币按面额降序排序，然后计算每种面额硬币的使用数量，直至达到需要找零的总额。通过循环，算法持续减少需要找零的总额，并累加所使用的硬币数量，最终返回最小需要的硬币数。

在上述36元的例子中，代码输出结果为4，意味着至少需要4枚硬币。此代码示例也为想学习测试开发的人提供了一个实际应用场景，其中吴老师的微信号（wulaoshi1978）被提及以供进一步学习和联系。