Describe a dyanmic programming solution to the problem of ma

Describe a dyanmic programming solution to the problem of making_change with the fewest number of coins.

Illustrate your technique with the example coinage of {1, 5, 8, 10} denomination to make change for the value of 26.

Solution

Say we are given coinage C = { C1, C2, ... Cn } with n coins of different values, and we want to make change for some value V ( V >= 0 )

Now, if V = 0, then clearly no coins are required at all i.e. answer should be 0

However if V > 0 , then we can reduce our problem in smaller subproblems ( smaller in sense, that we require to calculate answer for some other value W < V ) in the following manner :

We try each coin Ci from our coinage, given V >= Ci, and get minimum coin change answer for ( V - Ci )

Once we try it for all coins, we find minimum of all the answers, and adding 1 to it should give optimal value for V

i.e. making_change( V ) = min{ 1 + making_change( V - Ci ) }

where i varies from 1 to N, and V >= Ci

Now we have got a recursive solution, but its complexity is still exponential. To use the concept of dynamic programming, we store the results to avoid re-calculating them i.e. we assign an array of size V, and fill it with say -1. We then iterate from 1 to V, finding answer for all values so that when we try to find answer for V, we already have the answer to possible subproblems that might arise.

Writing code for DP solution now should be fairly straightforward.

Pseudo Code:

array[V]; //initializing all to -1

array[0] = 0;

for val = 1 to V:

for coin in {C1 , C2, ... Cn}:

if ( coin <= val ) : //we can use this coin

sp_result = array[ val - coin ]; //subproblem result

if ( sp_result != -1 and sp_result + 1 < array[val] ):

// some subproblem might have no change, and thus are set to initial value

array[ val ] = sp_result + 1;

return array[ V ]

Example:

C = {1,5,8,10} and V = 26;

Array be array of size 26 ( note that, I am starting index of array from 1, unlike in C/C++ )

26 being a big number, let me work the answer out till 5.

Array[0] = 0;

Array[1] = 1; //using coin of value 1, sp_result = Array[0], and Array[1] = sp_result + 1;

For Array[2], coin of value 1 is only one we can try, as rest are of larger values than 2

and using that sp_result = Array[1] = 1, and Array[2] = 1+1 = 2

For Array[3], we can try only 1, giving 3 as answer

Similarly for Array[4], we get 4

For Array[5], we can try coin 1 or 5,

if we try 1, sp_result = table[4] = 4 and we get answer as 5

if we try 5, sp_result = table[0] = 0 and we get answer as 1

As minimum answer makes it to Array[ val ] , Array[5] sets to 1

similarly it can be worked out till required val