最小硬币找零问题——回溯

Question

我正在尝试用最少的硬币数解决硬币找零问题使用回溯法。

我实际上已经完成了它，但我想添加一些选项来按其单位打印硬币数量，而不仅仅是总数。

下面是我的 python 代码。

def minimum_coins(coin_list, change):
min_coins = change 
if change in coin_list: 
    return 1
else:
    for coin in coin_list:
        if coin < change: 
            num_coins = 1 + minimum_coins(coin_list, change - coin)
            if num_coins < min_coins:
                min_coins = num_coins
return min_coins

coin_list = []
unit = input("Enter the Coin Unit\n")
#1 10 15 20
change = int(input("Enter the Total Change\n"))
#73
unit = unit.split()

for i in unit:
    coin_list.append(int(i))

min = minimum_coins(coin_list, change)
#print("You need 3 1's, 1 10's, 0 15's, 3 20's") <- I want to implement this option.
print("Total number of coins required is %s." % min) #7

我很难在我的代码中实现它。

因为回溯很复杂，我不知道如何按单位检查硬币数量。

Answer 1

可能的方式：

def minimum_coins(coin_list, change):
    min_coins = change
    if change in coin_list:
        return 1, [change]
    else:
        cl = []
        for coin in coin_list:
            if coin < change:
                mt, t = minimum_coins(coin_list, change - coin)
                num_coins = 1 + mt
                if num_coins < min_coins:
                    min_coins = num_coins
                    cl = t + [coin]
    return min_coins, cl

change = 73
coin_list = [1, 10, 15, 20]
min, c = minimum_coins(coin_list, change)
#print("You need 3 1's, 1 10's, 0 15's, 3 20's") <- I want to implement this option.
print("Total number of coins required is %s." % min, c) #7

>>>Total number of coins required is 7. [20, 20, 20, 10, 1, 1, 1]

最小硬币找零问题——回溯

Minimum Coin change problem - Backtracking

python

algorithm

backtracking

coin-change