如何使用递归函数进行硬币兑换？

Question

我尝试在Python中使用递归函数。我有一个场景，我生活在一个有5枚和7枚硬币的国家。我想象着去购物，拿到剩下的硬币。我试着从24岁到1000岁，我想知道：

• 对于24:[5,5,7,7]
• 对于25：[5,5,5,5,5]
• 第26条：[5,7,7,7]

我得到错误：'TypeError:'int'对象不可编辑'

你能帮我解决我的问题吗

amount = range(24,1000)
def change(amount):
    for i in amount:
        for s in range(1,100):
            for j in range(1,100):
                if i == (5*s + 7*j):
                    list = [s,j]
                    print(list)
                else:
                    coins = change(i - 5)
                    coins.append(5)

change(amount)

Answer 1

对于这种解决方案，关键的见解是，每一笔金额都可以表示为一套参考硬币或一套参考硬币加上一定数量的填充硬币。例如，如果金额为42，则可以表示为28+7+7或27+5+5+5

注：参考金额需要是从24开始到30的连续整数，以允许填充硬币的值为7。这是一个棘手的部分

解决方案：

def coin_count(amount, filler_coin_value=5):
    reference = {
        24: (7, 7, 5, 5), 
        25: (5, 5, 5, 5, 5),
        26: (7, 7, 7, 5), 
        27: (5, 5, 5, 5, 7), 
        28: (7, 7, 7, 7),
        29: (7, 7, 5, 5, 5),
        30: (5, 5, 5, 5, 5, 5)
    }
    coins = []
    while not amount in reference:
        amount -= filler_coin_value
        coins.append(filler_coin_value)
    coins.extend(reference[amount])
    
    return coins

虽然上述解决方案可行，但可以通过用一些（公认的棘手的）数学替换while循环来优化它

def coin_count_optimized(amount, filler_coin_value=5):
    reference = {
        24: (7, 7, 5, 5), 
        25: (5, 5, 5, 5, 5),
        26: (7, 7, 7, 5), 
        27: (5, 5, 5, 5, 7), 
        28: (7, 7, 7, 7),
        29: (7, 7, 5, 5, 5),
        30: (5, 5, 5, 5, 5, 5)
    }
    filler_count, off_by = divmod((amount - 24), filler_coin_value)
    coins = [filler_coin_value] * filler_count
    coins.extend(reference[24 + off_by])
    
    return coins

两种方法的时间比较：

import time

start_time = time.time()
for amount in range(24, 1000):
    coin_count(amount)
print("coin_count", time.time() - start_time)

start_time = time.time()
for amount in range(24, 1000):
    coin_count_optimized(amount)
print("coin_count_optimized", time.time() - start_time)

输出：

coin_count 0.022232770919799805
coin_count_optimized 0.0019953250885009766