Print result and not amout

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

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

That’s an interesting choice for the “no change” value. Another choice
would be nan from the math module (also obtainable as
float('nan')) which is a special float value for “not a number”.

def change_making(coins, n: int):
   [...]
   return m[-1][-1]

Here your function returns the bottom right corner of the matrix.

If you also want the coins used as well the simplest way is to have a
list and to add coins to it as they are used. Example (inside the coin
allocation function):

 # start empty at the top
 coins_used = []

in the branches where a coin is chosen for use, append the coin to the
list:

 coins_used.append(coin)

That appends a single con value to the list. If some step used multiple
coins in one go you could append several times.

At the end, instead of returning just the single value, return both the
original vaoue and the coins_used list:

 return m[-1][-1], coins used

Then collect both:

 nums = 1, 3, 5, 6, 7, 8
 m11, coins_used = change_making(nums, 13)
 print(m11)
 print(coins_used)

I’d make a point of putting some print() calls inside the function
where you append coins to ensure that you’re doing what you intend.
Remove those when the function works correctly.

Cheers,
Cameron Simpson cs@cskk.id.au

If it’s not homework then I would suggest built-in divmod. Divide amount with largest coin, repeat this on reminder and next largest coin until there is no reminder (coins must be sorted). Something like:

def change(amount, coins):
    returnable = []
    coins = sorted(coins, reverse=True)
    for coin in coins:
        quantity, amount = divmod(amount, coin)
        if quantity:
            returnable.extend([coin]*quantity)
        if not amount:
            break
    return returnable


coins = change(13, (1, 2, 3, 4, 5, 6, 7))

print(len(coins))
print(*coins)

2
7 6

coins = change(22, (1, 2, 4, 5))

print(len(coins))
print(*coins)

5
5 5 5 5 2

Hello,
Thank you for you reply. I implemented your code and it works seamlessly. However another user brought up the code can also be written using divmod, which defiantly shortens the length. Do you know if there are any issues that may occur by using divmod as opposed to my approach?
Best Regards,
Stan

Hello,
I had forgotten about divmod as I have never used it before. Thanks for you suggestion! And no, this is not homework, not anymore though, that would have been in good old c++.
Best Regards,
Stan Ulbrych