简述一个贪心算法的经典案例

一个经典的贪心算法案例是找零钱问题。假设你是一家商店的收银员，需要找给顾客一定面额的零钱。假设你有若干张纸币和硬币，它们的面额分别是 1 元、5 元、10 元、50 元、100 元、500 元，现在需要找给顾客 n 元的零钱。如何找钱使得所需的纸币和硬币数量最少？

这个问题可以使用贪心算法来解决。具体步骤如下：

1. 从面额最大的纸币开始，尽可能多地找给顾客该面额的纸币，直到无法再找该面额的纸币为止；
2. 如果还有剩余的钱，就继续从面额次大的纸币开始找，直到所有的钱都找完为止。

这个贪心算法的正确性可以证明，因为在每个阶段，我们都尽可能多地使用面额大的纸币，以便留下足够的小面额纸币和硬币，可以更容易地找给顾客剩余的零钱。因此，每个阶段的局部最优解也是全局最优解。