Hello,
I am playing around with the change making problem but I can’t seem to find a way to print the coins used in the optimal combination and not the amount of coins used. The base code is shown below.
def _get_change_making_matrix(set_of_coins, r: int):
m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
for i in range(1, r + 1):
m[0][i] = float('inf') # By default there is no way of making change
return m
def change_making(coins, n: int):
"""This function assumes that all coins are available infinitely.
n is the number to obtain with the fewest coins.
coins is a list or tuple with the available denominations.
"""
m = _get_change_making_matrix(coins, n)
for c, coin in enumerate(coins, 1):
for r in range(1, n + 1):
# Just use the coin
if coin == r:
m[c][r] = 1
# coin cannot be included.
# Use the previous solution for making r,
# excluding coin
elif coin > r:
m[c][r] = m[c - 1][r]
# coin can be used.
# Decide which one of the following solutions is the best:
# 1. Using the previous solution for making r (without using coin).
# 2. Using the previous solution for making r - coin (without
# using coin) plus this 1 extra coin.
else:
m[c][r] = min(m[c - 1][r], 1 + m[c][r - coin])
return m[-1][-1]
nums = 1, 3, 5, 6, 7, 8
print(change_making(nums, 13))
And I get the following result in my terminal:
2
However I would like to get a list of the coins used so the terminal should look like this:
2
7, 6
Does anyone know of a way to implement this into the code?
Best Regards,
Stan