Search code examples
pythonalgorithmbacktrackingcoin-change

Minimum Coin change problem - Backtracking


I'm trying to solve Coin change problem with minimum number of coins using backtracking method.

I've actually done with it, but I want to add some option that print the number of coins by its unit not only total amount.

this is my python codes below.

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

I'm struggling to implement this in my code.

cause back-tracking is complex, I can't get the idea how to check the number of coins by its unit.


Solution

  • Possible way:

    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]