1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It is not clear the problem you want to solve. Do you want the minimum number of coins to achieve a specific value? $\endgroup$ – Daniel Saad Jan 24 '18 at 12:03
0
$\begingroup$

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]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.