Printing actual solutions for the coin exchange problem
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 &amp; i = 0 \land k = 0\\
-\infty &amp; i = 0 \land k &gt; 0\\
S(i-1,k) &amp; i &gt; 0 \land V[i-1]-k &lt; 0\\
\max(S(i-1,k),S(i,k-W[i-1])) + 1 &amp; \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]$.