To find out denomination of the coins-CodePudding

I have the following code to find the minimum amount of exchangeable coins. How can I find out what denomination of the coins got there?

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: Input - 1 - the amount to be decomposed, 2 - denomination of coins

in:
6
1 3 4
    
out:
3 3

CodePudding user response：

Here is how to use dynamic programming to produce the answer.

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))

However for coins of very different sizes it is much more efficient to use A* Search. The heuristic is that the number of steps to finish is the number of steps that you have taken how much distance left / coin size. And then you ONLY move to smaller coins.