这种硬币兑换算法是如何工作的

Question

以下是从高到低排列的硬币面额列表。

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

金额为445。该功能的输出为

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

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

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)]