Printing actual solutions for the coin exchange problem

Question

As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight about it. Specifically, the following implementation of a tabulated-DP-based solution for this problems is presented as follows:

def count(S, m, n ):
    # If n is 0 then there is 1
    # solution (do not include any coin)
    if (n == 0):
        return 1
    # If n is less than 0 then no
    # solution exists
    if (n < 0):
        return 0;
    # If there are no coins and n
    # is greater than 0, then no
    # solution exist
    if (m <=0 and n >= 1):
        return 0
    # count is sum of solutions (i)
    # including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

However, this only counts the number possibles solutions.

Question: How can I actually save these solutions for post-processing?

Previous research: In this very helpful video: https://www.youtube.com/watch?v=ENyox7kNKeY they explain how to use an array of parent pointers, to generate the actual solutions, however, I am having issues with implementing this approach with the previous tabulated solution. Any hint?

Answer 1

Assuming that you want the minimum number of coins to achieve a desired value and that you have a sufficient number of coins of every value we have this relation of recurrence:

Let $S(i,k)$ be the minimum number of coins to achieve the value $k$ considering the first $i$ coins. Also, let $V[i]$ be the value of the $i$-th coin.

So:

$$S(i,k) = \begin{cases} 0 & i = 0 \land k = 0\\ -\infty & i = 0 \land k > 0\\ S(i-1,k) & i > 0 \land V[i-1]-k < 0\\ \max(S(i-1,k),S(i,k-W[i-1])) + 1 & \text{otherwise} \end{cases}$$

• Case 1 = Base case, considering the first 0 coins and the value 0 you pay 0 coins.
• Case 2 = Base case, considering the first 0 coins and a value greater than 0 you cant pay the value.
• Case 3 = Considering the first $i$ coins you can pick the solution to pay the value $k$ without considering the $i$-th coin, which is in $S(i-1,k)$.
• Case 4 = Considering the first $i$ coins, you should maximize between the solutions considering the $i$-th coin and not considering it. If the i-th coin is considered, you increment the number of coins in the solution, because you used the $i$-th coin.

A recursion based solution follows in verbatim from this relation of recurrence, but in Dynamic Programming you will replace a recursive call by a table lookup. So basically, where is $S(a,b)$ you will replace by a table access $S[a,b]$.