Dynamic change-making algorithm that returns actual list of coins used

Question

I'm trying to adjust the code from the wikipedia:

https://en.wikipedia.org/wiki/Change-making_problem#Implementation

To also output the list of coins used, not only the number of coins used. That is, for instance:

change_making([6, 8, 12], 52) outputs 5 which is correct (12+12+12+8+8 = 52).

The problem is that I want to get output in this format [12, 12, 12, 8, 8] instead of just 5 and I have no idea how to do that.

The code in question:

def _get_change_making_matrix(set_of_coins, r):
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]

    for i in range(r + 1):
        m[0][i] = i

    return m


def change_making(coins, n):
    """This function assumes that all coins are available infinitely.

    n is the number that we need to obtain with the fewest number of coins.

    coins is a list or tuple with the available denominations."""

    m = _get_change_making_matrix(coins, n)

    for c in range(1, len(coins) + 1):

        for r in range(1, n + 1):

            # Just use the coin coins[c - 1].
            if coins[c - 1] == r:
                m[c][r] = 1

            # coins[c - 1] cannot be included.
            # We use the previous solution for making r,
            # excluding coins[c - 1].
            elif coins[c - 1] > r:
                m[c][r] = m[c - 1][r]

            # We can use coins[c - 1].
            # We need to decide which one of the following solutions is the best:
            # 1. Using the previous solution for making r (without using coins[c - 1]).
            # 2. Using the previous solution for making r - coins[c - 1] (without using coins[c - 1]) plus this 1 extra coin.
            else:
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])

    return m[-1][-1]

Any help/suggestion would be greatly appreciated.

------------- EDIT -------------

The solution (comments removed):

def _change_making(coins, n):
    m = [[0 for _ in range(n + 1)] for _ in range(len(coins) + 1)]
    for i in range(n + 1):
        m[0][i] = i

    for c in range(1, len(coins) + 1):
        for r in range(1, n + 1):
            if coins[c - 1] == r:
                m[c][r] = 1
            elif coins[c - 1] > r:
                m[c][r] = m[c - 1][r]
            else:
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])

    i = len(coins)
    j = n
    ret = {k: 0 for k in coins}
    while j != 0:
        if m[i][j - coins[i - 1]] == m[i][j] - 1:
            ret[coins[i - 1]] += 1
            j = j - coins[i - 1]
        else:
            i = i - 1

    return ret

To find the closest * solution:

def change_making(coins, n):
    try:
        return _generate_packing(coins, n)
    except:
        return generate_packing(coins, n + 1)

For instance change_making([2, 5], 8)

{2: 2, 5: 1}

Because 9 is the closest possible solution.

• By closest I mean a solution that is possible to satisfy but above the original request. For instance if we need to return £8 in change and we do not have the exact change, well, we will return £9 because we do have change for that.

Answer 1

Here are steps how you can do it -

1)Start with i=len(coins) and j=n ie end of your array(or list) m

2)Now we know a coin of value coins(i-1) is chosen if m[i][j] uses exactly one more coin than m[i][j-coins[i-1]].

3)If this doesnt happen we check the other coins(coins at lower index in list) for same condition.

Example-

At start we have value 52 and we have solved that it needs 5 coins using your your function.

We use first coin of 12 only if for value 40(ie 52 -12) we need 4 coins and similarly for for 2nd and 3rd 12 valued coin.

But we cant use fourth 12 coin as value 4(ie 16-12) cant be achieved using 1 coin.

Here is code snippet to do same(you can it use at end of your function instead of return statement) -

i=len(coins)
j = n
while(j!=0):
    if m[i][j-coins[i-1]] == m[i][j]-1:
        print(coins[i-1])
        j=j-coins[i-1]
    else:
        i=i-1