python-3.x - 这种硬币找零算法是如何工作的？

Question

这是从高到低排序的硬币面额列表。

coinage = [500, 200, 100, 50, 20, 10, 5, 1]

金额为445。这个函数的输出是

[(2, 200), (2, 20), (1, 5)]

我真的对算法感到困惑。它是如何工作的？

标签： python-3.x

Answer 1

你可以使用这样的东西。由于coinage列表已经反向排序，因此事情变得容易。您只需要遍历列表并执行逻辑：

coinage = [500, 200, 100, 50, 20, 10, 5, 1]
money = 445

sum, lst = 0, []
for x in coinage:
    if x <= money:
        lst.append((money // x, x))
        sum = (money // x) * x
        money -= sum

print(lst)
# [(2, 200), (2, 20), (1, 5)]