头歌实验六 贪婪算法，找零钱

贪婪算法是一种基于贪心策略的算法，它在每一步都选择当前看起来最优的选项，以期望最终得到全局最优解。找零钱问题是一个经典的使用贪婪算法解决的问题。

假设你需要找零 $n$ 元钱，你手里有若干种面值的硬币，如 1 元、5 元、10 元、20 元、50 元、100 元等。现在要求尽可能少地使用硬币找零，该怎么办？

一个简单而有效的贪婪策略是每次选取面值最大的硬币进行找零。在找零过程中，每次都用尽可能多的面值最大的硬币，直到找完为止。这个方法的正确性可以通过反证法证明。

下面是一个 Python 实现：

def change(n, coins):
    """
    在硬币列表 coins 中找零 n 元钱，返回所需的硬币数量。
    """
    coins.sort(reverse=True)  # 按面值从大到小排序
    count = 0
    for coin in coins:
        while n >= coin:
            n -= coin
            count += 1
    return count

这个函数接受两个参数：要找零的金额 $n$ 和硬币列表 coins。它首先按硬币面值从大到小排序，然后从大到小遍历硬币列表，每次用尽可能多的当前面值的硬币进行找零，直到零钱全部找完为止。

例如，如果要找零 63 元，可用的硬币面值分别为 1 元、5 元、10 元、20 元和 50 元，可以这样调用该函数：

coins = [1, 5, 10, 20, 50]
n = 63
count = change(n, coins)
print(count)  # 输出 5

这个例子中，找零 63 元需要 5 个硬币，分别是 50 元、10 元、1 元、1 元、1 元。