货币系统找零贪心算法

货币系统找零问题是贪心算法的一个经典应用。贪心算法的思想是每次选择当前看起来最优的解决方案，而不考虑全局最优解。在货币系统找零问题中，我们需要找零的钱数为n，我们可以使用的硬币面额为d1、d2、……、dm。假设这些硬币面额按照从小到大的顺序排列。那么，我们可以按照以下步骤来使用贪心算法解决货币系统找零问题：

1. 初始化一个空的列表result，用于存储找零的硬币。
2. 从面额最大的硬币开始，如果当前硬币的面额小于等于剩余需要找零的钱数n，则将该硬币加入到result列表中，并将n减去该硬币的面额。
3. 如果当前硬币的面额大于剩余需要找零的钱数n，则跳过该硬币，考虑下一个面额更小的硬币。
4. 重复步骤2和步骤3，直到n等于0，表示已经找到了所有的硬币。

下面是一个Python实现的例子：

def greedy_coin_change(n, coins):
    coins.sort(reverse=True) # 将硬币面额从大到小排序
    result = [] # 存储找零的硬币
    for coin in coins:
        while n >= coin:
            result.append(coin)
            n -= coin
    return result

# 示例
n = 36
coins = [1, 5, 10, 20]
result = greedy_coin_change(n, coins)
print(result) # 输出 [20, 10, 5, 1]