找出硬币的面额

Question

我有以下代码来查找可交换硬币的最小数量。我怎样才能知道那里有什么面额的硬币？

def get_min_coin(coins, val):
if val < 0:
return -1
max_val = val + 1
min_coins = [max_val] * (val + 1)
min_coins[0] = 0
for coin in coins:
for v in range(coin, val + 1):
min_coins[v] = min(1 + min_coins[v - coin], min_coins[v])
return min_coins[-1]
change = int(input())
coins = list(map(int, input().split()))
get_min_coin(coins , a)

UPD:输入-1-要分解的金额，2-硬币的面额

in:
6
1 3 4

out:
3 3

Answer 1

以下是如何使用动态编程来产生答案。

def get_min_coin(coins, val):
if val < 0:
return None
max_val = val + 1
min_coins = [(max_val, None)] * (val + 1)
min_coins[0] = (0, None)
for coin in coins:
for v in range(coin, val + 1):
min_coins[v] = min((1 + min_coins[v - coin][0], coin), min_coins[v])
if min_coins[-1][1] is None:
return None
else:
answer = []
while 0 < val:
answer.append(min_coins[val][1])
val -= min_coins[val][1]
return answer
change = 10 # int(input())
coins = [3, 4, 1] # list(map(int, input().split()))
print(get_min_coin(coins , change))

然而，对于大小非常不同的硬币，使用A*搜索要高效得多。启发式是，要完成的步数是你所走的步数+剩余距离/硬币大小。然后你只能换更小的硬币。