what is a good technique to output a solution using dynamic programming?

1
votes

This question is specifically addressed towards the coin change problem. I know the algorithm to find the optimal number of coins used to find change for any amount, and I also understand it but what I don't understand is how could I "mark" if you will the path taken to find such solution. I have tried to use parent pointers, which I'm sure is the way to do it, but I simply don't know how I would implement it. Here's an example. Example: given coin denominations: 1, 10, 25 Change: 30 Optimum solution requires: 3 coins Coins used: 10, 10, 10

I am not really that good at solving dynamic programming problems.

1
algorithmrecursiondynamic-programmingcoin-change
Assume you know optimal solution for 1 through 29. How could you use it to find solution for 30? – ElKamina
sorry, I forgot to let you guys know that my current solution to the problem is only kept in an array, I'm not making the table. So I have the solution from 1 -29 but of number of coins used, not which coins. I'm sorry if this should be intuitive but it really isn't to me. I guess my question is: If I were to implement a 2d table with amounts from 0 to n as rows and coin denominations from 1 to k as columns, what would be the values of each cell and how would I calculate them? – Sektrax
You can solve it more efficiently. Keep a pointer to the previous optimal solution from which the current optimal solution is derived. Eg. For 10 have a link to zero. For 20 link to 10, and, for 30 link to 20. Now all you have to do is backtrack. 30's link is 20, so that is 30-20 = 10, 20's link is 10-> 20-10 = 10 and 10-0=10. That is how you get 3 10s – ElKamina

1 Answers

2
votes

You know that T[30] = 3. You must find a T[30-c] = 2, trying all c in {1, 10, 25}. As T[30-10] = 2, you know you'll use a 10 cents coin and now must solve the problem for T[20].

Repeat this until T[0] = 0.