如何计算硬币兑换问题中的发生次数

Question

我有一堆现金票据[5, 10, 20, 50, 100, 500]给定一个值x，找到与该值相加的最小可能票据，然后返回这些票据在数组中的出现次数。我们假设我们只能接收被min(cash) = 5整除的数字

例如

x = 5:
    return [1, 0, 0, 0, 0, 0]

以最少数量的音符接收5，5出现一次

另一个例子

x = 1000
    return [0, 0, 0, 0, 0, 2]

因为最少的钞票是两张500美元。它们出现两次。 这应该很容易，也许是的，我想我快到了，但似乎无法绕过最后的障碍

到目前为止，我的代码是：

def atm(x, cash=[5, 10, 20, 50, 100, 500]):
    count_5 = 0
    count_10 = 0
    count_20 = 0
    count_50 = 0
    count_100 = 0
    count_500 = 0
    if x == 5:
        return [1, 0, 0, 0, 0, 0]
    elif x == 10:
        return [0, 1, 0, 0, 0, 0]
    elif x == 20:
        return [0, 0, 1, 0, 0, 0]
    elif x == 50:
        return [0, 0, 0, 1, 0, 0]
    elif x == 100:
        return [0, 0, 0, 0, 1, 0]
    elif x == 500:
        return [0, 0, 0, 0, 0, 1]

    flag = None
    for c in cash:
        if c < x:
            flag = c
    temp_balance = round(x - flag, 2)

    if flag or temp_balance == 5:
        count_5 += 1
    if flag or temp_balance == 10:
        count_10 += 1
    if flag or temp_balance == 20:
        count_20 += 1
    if flag or temp_balance == 50:
        count_50 += 1
    if flag or temp_balance == 100:
        count_100 += 1
    if flag or temp_balance == 500:
        count_500 += 1

    return [count_5, count_10, count_20, count_50, count_100, count_500]


print(atm(150))

这返回的是[1, 1, 1, 1, 1, 1]，这不正确，正如我所期望的[0, 0, 0, 1, 1, 0]。我做错了什么？如何修复

我已经部分使用了这个YouTubevideo，但是我没有使用递归

我也在考虑这个问题的时间复杂性，但在创建更高效算法的早期阶段。因此，如果有更好的方法代替所有这些if{}语句，那么我想从中学习

Answer 1

您只需要在cash值上循环，从x中减去它们：

def atm(x, cash=[10, 20, 50, 100, 500]):
    ret = [0] * len(cash)
    for idx,d in enumerate(reversed(cash)):
        while x >= d:
            x -= d
            ret[idx] += 1
    
    return list(reversed(ret))
        
print(atm(450))

输出：

[0, 0, 1, 4, 0]