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

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]

Answer 2

为什么看到[1, 1, 1, 1, 1]（全部1）的部分问题是因为if语句中有一个错误：

    if flag or temp_balance == 100:

这不检查是否flag is 100 or temp_balance is 100，只检查是否flag is non-zero OR temp_balance is 100，每次迭代都是这样

其他一些问题：

1. 您有一个cash参数作为输入，但它不一定与用于跟踪注释数量的变量相关。您应该找到一些方法来根据初始cash数组跟踪笔记。这可以像创建另一个长度相同的数组一样简单，该数组使用所有0初始化，用于保存每个位置的现金票据计数note_count = [0 for _ in cash]
2. 不要试图为精确匹配而退出特例。它只会让你的代码变长
3. 你不能用贪婪算法来解决这个问题。要使它正常工作，您需要类似于动态编程的东西。考虑你的现金值^ {< CD7> }，你有^ {CD8}}。如果你使用贪婪算法，你会记3个音符，1个音符是200，2个音符是50，但是你可以用2个音符是150

---

时间复杂性（用大O表示法表示，如O(n)）是关于执行长度如何作为某个输入的一个因素而增长的

最典型的情况是n表示算法迭代的项数（但它可以表示执行某些按位数学运算的算法的输入的位长度）。如果你的现金系统的上限是某个数字，比如说10，那么你用来寻找下一张钞票的循环将变成一个常数，因为你有一个常数的迭代次数来寻找下一张钞票。事实上，在你的情况下，你有一个恒定的时间复杂性，关于选择一张纸币，因为你已经明确写出了6个现金纸币的情况。这里的变量是您的输入量，因此您的时间复杂度将取决于将给定量减少到0所需的时间。你应该能够相当容易地找到这个数字（想想需要最多纸币的金额是多少，然后想想所有大于这个数字的金额）

时间复杂性与两个操作之间的效率无关

当您谈论if, else if语句以及如何生成更高效的代码时，您可能会正确地说“一个构造比另一个构造更高效或更快”，但这不是时间复杂性的含义。时间复杂度是指执行长度作为某个输入的一个因素是如何增长的。例如，通过使用字典，您可以做出稍微更有效的“选择”构造。字典具有固定的时间访问，因此无论字典中有多少项，您的时间访问都是O(1)。但是如果if/else语句的数量是恒定的，那么它也是O(1)，因为if/else语句不会增长。它可能会慢一些，但它的复杂性仍然是不变的

Answer 3

我认为这就是您需要的（很抱歉重写了您的代码）：

def atm(x, cash=[100, 50, 20]):
xCpy = x

notes = [0 for x in range (len(cash))]

i = len(cash)-1
for note in cash:
    while note <= xCpy:
        xCpy -= note

        notes[i] += 1
    i -= 1

return notes

print(atm(40))