python贪心算法找零问题

找零问题是一个经典的贪心算法问题。假设你是一名收银员，需要找给顾客一定面额的纸币和硬币，问如何找零才能使用最少的纸币和硬币。

假设你有以下面额的纸币和硬币：1元、5元、10元、50元、100元。现在需要找给顾客47元的零钱。如何使用最少的纸币和硬币找零？

我们可以使用贪心策略，即每次尽可能多地选择面额最大的纸币或硬币。对于这个例子，我们可以按照以下步骤找零：

1. 选择面额最大的纸币50元，找零47元，剩下需要找零3元。

2. 选择面额最大的硬币1元，找零3元，剩下需要找零0元。

因此，我们需要找给顾客1张50元和3张1元的纸币和硬币。使用贪心算法可以得到最优解。

以下是使用Python实现的贪心算法找零的代码：

def change(n):
    coins = [100, 50, 10, 5, 1] # 面额
    counts = [0] * len(coins) # 纸币和硬币的数量
    for i, coin in enumerate(coins):
        count = n // coin
        counts[i] = count
        n -= count * coin
        if n == 0:
            break
    return counts

其中，n表示需要找零的金额。coins表示纸币和硬币的面额，counts表示纸币和硬币的数量。我们依次枚举每种面额的纸币和硬币，每次选择尽可能多的纸币和硬币，直到找零完毕。最后返回纸币和硬币的数量即可。

希望这个例子能够帮助你理解贪心算法的思想。