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.
Possible way: