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[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:
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?