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

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

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

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

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

相关问题

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

一个经典的贪心算法案例是找零钱问题，假设你是一家商店的收银员，你需要找给顾客最少数量的硬币找零。假设你有以下面额的硬币：1元、5元、10元、50元、100元。现在顾客需要找零n元钱，问你最少需要给顾客几个硬币。

贪心算法解决这个问题的思路是：每次找零时，优先使用面额最大的硬币，直到找完n元钱为止。具体实现过程如下：

1. 初始化需要找零的总金额为n，硬币数num=0。

2. 对于当前的n元钱，如果n大于等于100元，则找一张100元的钞票，并将n减去100；

3. 如果n小于100元但大于等于50元，则找一张50元的钞票，并将n减去50；

4. 如果n小于50元但大于等于10元，则找一张10元的钞票，并将n减去10；

5. 如果n小于10元但大于等于5元，则找一张5元的钞票，并将n减去5；

6. 如果n小于5元但大于等于1元，则找一张1元的钞票，并将n减去1；

7. 如果n等于0，则找零完成，此时所用的硬币数即为最少硬币数。

这个算法可以保证每次找零使用的硬币面额最大，因此所用硬币数一定是最少的。