Minmum Coin Change Problem

Problem Statement:

Every country has different type of bank notes and face value of each banknote is different.  Like in india we have banknote of 1, 2, 5, 10, 20 .... and so on :). So in today problem we only focus on lower bank note value not bigger.

Problem is if you have 1, 2, 5, 10 bank notes and you want to make change for the 17. There are multiple solution for that:

{10,5,2}

{5,5,5,2}

{10,5,1,1}

So we come across number of solution. Our aim is develop an algorithm with minimum number of coins So in our case we need a optimal solution  {10,5,2}.

We can write the problem in following manner:

Given a set of integer value Let {r1, r2 , r3... , rn } where r1 =1  and rj < rj+1 for 1<= j <= n-1, and a positive value W(17 from above). find a non negative set of integers which minimize.

n

∑xj

j=1

such that

n 

∑rjxj = W

j=1

Solution:

We will follow the approach of calculating change require for the all the x where x < w. 

Let suppose c[p] is minimum change (rupees change) require for the p rupees. For calculating the c[p] we need to calculate c[x] where x < p.

So what will be the c[p] ? 

c[p] = min : ri <= p { c[p - ri ] } + 1 if p > 0

            i                           0  if p = 0

Let understand the solution if we need a change for 7 rupees and we have coin for 1, 2 , 5.

We need to calculate c[7] with r = {1,  2,  5}.

First Calculate c[0] = 0  as p = 0

c[1] = min {c[1-1] } + 1  // We cannot consider 2 and 5 as the ri <= p condition does not met 2  > 1 and 5 > 1.

C[1] = min {0} + 1 = 1

C[2] = min {c[2-1],  c[2-2] }  + 1

c[2] = min {1 , 0} + 1

c[2] = 1 So we can calculate c[2] by just one coin 2

c[3] = min {c[3-1],  c[3-2] }  + 1

       = min {c[2] , c[1] } + 1

       = min {1 , 1} + 1

       = 1+1 = 2 // So we need two bank note for change of 3.

c[4] = min {c[4-1],  c[4-2] }  + 1

       = min {c[3] , c[2]} + 1

      = min {2, 1} + 1

     = 1+1 = 2 // right we need only two coin (2,2)

c[5] = min {c[5-1],  c[5-2] , c[5-5] }  + 1

       = min {c[4] , c[3] , c[0] } + 1

      = min {2 , 2 , 0} + 1

      = 1 // right now we have bank note 5 as ri <= p condition met where ri is bank note which is equal to 5 and p is also 5 we need change of 5.

c[6] = min {c[6-1],  c[6-2] , c[6-5] }  + 1

       = min {c[5] , c[4] , c[1]} + 1

      = min {1, 2, 1} + 1

      = 1 + 1 =  2 // (5, 1) or (1 , 5)

c[7] = min {c[7-1],  c[7-2] , c[7-5] }  + 1

       = min {c[6] , c[5] , c[2]]} + 1

       = min {2 , 1 , 1} + 1

      = 2 // (5,2 ) or (2, 5)

So our solution approach is right. 

How it works ? 

Just forget the problem and suppose you want to reach at value S with minimum addition of the values from the set {c1 ,  c2 ,  c3 , --- cn}. What approach you will take.

Greedy Approach:

Take the larger value from set try to add it two times or three times and check if it is larger than S. Then try to add lower value and so on. is it work every time ?
Try on this Sum = 30
{1, 15, 25}

No it will not work for the above case :).

Recursive Approach:

Let suppose you know the minimum number from the set require to make the sum S and it is following:

{C1, C2,  C2, C3}

We know one fact here if i do S-C3 the {C1, C2, C2} is the minimum numbers require for the sum C1+C2+C2.

Confusing ?

Let you have to make the sum 17 with the value {1, 3, 5}

then value is {1, 1, 5, 5, 5}

I am picking up the last value 5 and subtract it from 17. 17-5 = 12

and the remaining number is {1, 1, 5 , 5}.

So it is minimum number require for 12.

Now if i pick the last one again then {1, 1, 5} is minimum for 7.

So what i am doing here i am just subtracting the given value(17) from the set of to the number {1, 3, 5}.

If sum is 4 then we have {1, 3}

4-3 = 1 so we require only one value from the set that is {1} and it is true.

So can we apply this solution to our problem ?

Let suppose you have to make the coin change for 17 with the coin {1, 3, 5}.

Try to calculate C[17 - 5] , C[17 - 3] , C[17 -1] ? Which one is minimum add 1 into that. It is your solution :). So for this you need to calculate c[12], c[14] , c[16]. In this manner we need to calculate 

c[7],c[11], c[15] and so on.

Running Time:
Recursive approach will provide you the right solution but it will take longer time to execute. Because it will re compute the solution again again for the same number. Like for c[12] it will calculated three time one for c[17 - 5], c[15-3], c[13-1].

Can we improve that? yes the approach is dynamic programming.

Dynamic Approach:

We can solve any problem with dynamic programming if problem solution has following two attributes:

1) optimal substructure : If optimal solution is constructed from the optimal solution of subproblem then the solution has optimal sub structure.

2) overlapping subproblem :  If problem can be broken into sub problem which are used several times.

So both the attributes can be applied on our problem so we can solve our problem by dynamic programming.

So we Follow the same solution as explain above in Solution section.
Let suppose you have to calculate the minimum coins require for rupees j. Then you need to calculate minimum coin for all the value less than j(Optimal substructure).

Running Time:
We need to calculate minimum coin change for all the value less than j. So one loop is require for iteration to 1...j. In each value we need to check for the minimum value by iteration over all the coin value. So nested loop is require for the solution.

Complexity will be O(jl).
Where j is value for which minimum coin change need to be calculate.
l is length of the coin set.  


Code:

int findMinimumCoinChange(int rs, const int coinSetPtr [], size_t coinSetLength){

    int minCoinValues[rs+1];

    int finalSolutiuon = 0;

    memset(minCoinValues, -1, sizeof(minCoinValues));

    minCoinValues[0] = 0;

    //Calculating the solution from 1 to given rs.

    for(int i = 1; i <= rs ; i++){

        int solution[coinSetLength];

        memset(solution, -1, sizeof(solution));

        // All possible solution for the value i

        for (int j=0; j < coinSetLength; j++) {

            if(coinSetPtr [j] <= i){

                solution[j] = minCoinValues[i - coinSetPtr[j]] + 1;

            }

        }

        

        finalSolutiuon = -1;

        // Minimum Possible solution for the value i

        for(int k=0;k < coinSetLength;k++){

            if(solution[k] > 0 ){

                if(minCoinValues[i] == -1 || solution[k] < minCoinValues[i]){

                    minCoinValues[i] = solution[k];

                }

            }

        }

        

        

    }

    return minCoinValues[rs];

}

You can download the full source code from the link

Now we are done with the coin change problem :).