ATM 现金提取算法仅使用 20 美元和 50 美元纸币分发纸币

Question

我想首先承认我知道在 SO 和其他网站上有很多类似的问题，但是对于我的具体示例，所有提出的解决方案似乎都有相同的问题。

仅使用 $20 和 $50 纸币，我想计算加起来等于所需金额的较少数量的纸币。

尽管我的问题与语言无关，但为简单起见，我将使用 Python。我看到很多人提出这样的建议：

def calculate_notes(amount, notes):
    remainder = amount
    results = {}

    for note in notes:
        n, remainder = divmod(remainder, note)
        results[note] = n

    return results

但是，上面的方法在许多不同的场景下返回了错误的结果，这里有几个：

print(calculate_notes(110, [50, 20]))  # Outputs {50: 2, 20: 0}, it should be {50: 1, 20: 3}
print(calculate_notes(130, [50, 20]))  # Outputs {50: 2, 20: 1}, it should be {50: 1, 20: 4}

我的意思是，我可以通过添加一堆“if”语句来使其工作，但我想知道是否有办法 正确计算它.

可以忽略 $10、$25 和 $30 等无效金额。

Answer 1

时间复杂度- O(1) 循环的最坏情况将运行 5 次因此保持不变。

空间复杂度- O(1)

代码：

def calculate_notes(amount, notes):
    
    #Edge case amount=0
    if amount==0:
        return "Denomination not possible"
    options=[
        (0, {50: amount//50}),
        (10, {50: (amount//50)-1, 20:3}),
        (20, {50: amount//50, 20:1}),
        (30, {50: (amount//50)-1, 20:4}),
        (40, {50: amount//50, 20:2})
    ]
    for remainder,result in options:
        if amount%50==remainder and result[50]>=0: #result[50]>=0 for the cases like {amount: 10,30}
            return result
    return "Denomination not possible"


print(calculate_notes(110, [50, 20]))  
print(calculate_notes(20, [50, 20]))   
print(calculate_notes(10, [50, 20]))   

归功于@user3386109。而不是创建选项

nested_list

创建

dictionary

.

代码：

def calculate_notes(amount, notes):
    #Edge case amount=0
    if amount==0:
        return "Denomination not possible"
    options={
        0: {50: amount//50},
        10: {50: (amount//50)-1, 20:3},
        20: {50: amount//50, 20:1},
        30: {50: (amount//50)-1, 20:4},
        40: {50: amount//50, 20:2}
    }
    remainder=amount%50
    if remainder in options.keys() and options[remainder][50]>=0:
        return options[remainder]
    return "Denomination not possible"

输出：[两个代码]

{50: 1, 20: 3}
{50: 0, 20: 1}
Denomination not possible

Answer 2

我根据@user3386109 的建议提出了以下实现。

def calculate_notes(amount):
    notes_fifty, remainder = divmod(amount, 50)
    notes_twenty = 0

    if remainder != 0:
        if remainder % 20 != 0:
            notes_fifty -= 1
            remainder += 50

        notes_twenty = int(remainder / 20)

    return {'50': notes_fifty, '20': notes_twenty}

# Test with amounts between 40 and 200
for amount in range(40, 210, 10):
    notes = calculate_notes(amount)
    print(f'Amount {amount}', notes)
    assert (notes['50'] * 50) + (notes['20'] * 20) == amount

输出

Amount 40 {'50': 0, '20': 2}
Amount 50 {'50': 1, '20': 0}
Amount 60 {'50': 0, '20': 3}
Amount 70 {'50': 1, '20': 1}
Amount 80 {'50': 0, '20': 4}
Amount 90 {'50': 1, '20': 2}
Amount 100 {'50': 2, '20': 0}
Amount 110 {'50': 1, '20': 3}
Amount 120 {'50': 2, '20': 1}
Amount 130 {'50': 1, '20': 4}
Amount 140 {'50': 2, '20': 2}
Amount 150 {'50': 3, '20': 0}
Amount 160 {'50': 2, '20': 3}
Amount 170 {'50': 3, '20': 1}
Amount 180 {'50': 2, '20': 4}
Amount 190 {'50': 3, '20': 2}
Amount 200 {'50': 4, '20': 0}

Answer 3

请注意

5 * 20 = 2 * 50

这就是为什么我们在最佳解决方案中最多有

4

20

的音符（我们可以将

5

的

20

音符更改为

2

的

50

音符）。让我们检查所有 (

0, 1, 2, 3, 4

) 可能性并在无法交换时返回

(-1, -1)

：

def Solve(cash):
    if cash < 0 :
        return (-1, -1)
    
    for twenty in range(5):
        if ((cash - 20 * twenty) % 50 == 0):
            return (twenty, (cash - 20 * twenty) // 50)
            
    return (-1, -1)

这里我们有

O(1)

时间和空间复杂度：对于每个

cash

我们应该检查最坏情况下的

5

情况。

演示：

print(Solve(20))
print(Solve(100))
print(Solve(120))
print(Solve(123))

输出：

(1, 0)     # one 20, no 50
(0, 2)     # no 20, two 50s
(1, 2)     # one 20, two 50s
(-1, -1)   # not possible