Coin Change Problem

Problem Statement: 
               (Coin Change Problem)
Given coins V_{1 ,} V₂ , V₃ , .....V_n and amount W , find the minimum number of coins that sums to W.
Assume there are unlimited coins for each V_i    

V1	V2	V3	V4	V5	V6
1	3	6	12	24	30

W=53

Note : Unlimited number of coins for each coin value.

Solution : 

There is Greedy as well as dynamic approach for this , the shopkeeper uses Greedy Algorithm for large value of W, which may not be optimal at times.
          
Executing Greedy approach the result will be

1 x 30 + 1 x 12 + 1 x 6  +  1 x 3 + 2 x 1 = 53  ( 6 coins)

Whereas the optimal Solution using Dynamic Programming is  2 x 24 + 1 x 3 + 2 x 1= 53 (5 coins) 

I. Greedy Approach :
              Arrange the coins in reverse order , and if the coin value V_i  is lesser than W , subtract that value from from W ,

Algorithm:

1.  Arrange Coins in reverse Order
2.  If Coin value V_i  is lesser the W , subtract that V_i from W and print V_i, Else move to next coin value
   
3.  Repeat step 2 until  W becomes 0 and all coins are traversed. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

/** * Pass the array in descending value * @param coins : value of coins * @param size : number of coins * @param W : change required for the amount */ public static void greedyCoinChange(int coins[] , int size , int W ) { int i=0; while (W != 0 && i < size) { if( coins[i] > W) i++; else { System.out.println(coins[i]); W = W - coins[i]; } } }

II. Dynamic Programming

       Dynamic Programming is used where solutions of same problem is needed again and again.

             For the given problem to solve using dynamic programming we will have to develop an Optimal Sub structure as done in every dynamic problem , we need to ensure that solution to every sub-problem is optimal and combined result also produces optimal solution.
Every Dynamic Programming problem has the following properties:
a) Optimal Sub- Structure
b) Overlapping sub-problem

The given problem is optimal sub- problem as well , so we can use recursion as well to count the number of coins required. This problem can be solved with help of a beautiful equation below , and with the mighty power of recursion applied on the equation, therefore optimal equation is for the optimal sub-structure is :

     f  (W) =min_{i=1 to N}     {  f (W – V_i ) }  + 1     for i=1....N    for all  V_i < W

where f  (W) is minimum number of coins required to make change for amount W.

Lets expand the above equation :
 f  (W) =min_{i=1 to N} {  f (W – V₁) ,  f (W – V₂) , f (W – V₃), .............f (W – V_N) }  + 1

                                                                                      
Note:  f  (0) = 0 , i.e. number of coins required to change 0 is 0.

Now let us illustrate the above equation  with a smaller  data for the problem

 W = 5

V1	V2	V3
1	2	3

 
f  (1) = min_{i=1 to N}   {  f  (1 - V₁) } + 1  =  min_{i=1 to N}   {  f  (0) } + 1  = 1
f  (2) = min_{i=1 to N}   {  f  (2 - V₁) ,f  (2 - V₂) } + 1  
            =  min_{i=1 to N}   {  f  (1) ,  f  (0) }  + 1

            =  min { 1 , 0 }  + 1 = 1
f  (3) = min_{i=1 to N}   {  f  (3 - V₁) ,f  (3 - V₂) , f  (3 - V₃) }  + 1 
             = min_{i=1 to N}   {  f  (2) ,f  (1) , f  (0) }  + 1 

             = min { 1 , 1 ,  0 } + 1 = 1
f  (4) = min_{i=1 to N}   {  f  (4 - V₁) ,f  (4 - V₂) , f  (4 - V₃) }  + 1
            = min_{i=1 to N}   {  f  (3) ,f  (2) , f  (1) }  + 1  

             = min { 1 , 1 ,  1 } + 1 =2

f  (5) = min_{i=1 to N}   {  f  (5 - V₁) ,f  (5- V₂) , f  (5 - V₃) }  + 1
            = min_{i=1 to N}   {  f  (4) ,f  (3) , f  (2) }  + 1  
      
             = min { 1  , 1 , 1 } + 1 = 2

The Matrix representation of the values calculated.

V\W	0	1	2	3	4	5
0	0	1	1	1	-	-
1	0	-	2	2	2	2
2	0	-	-	2	2	2
3	0	-	-	-	2	2

 The blue colored cell is minimum in the column for every value of 'w' till 'W'.

Algorithm :

Change(coins, W, size)
1 fValues[0] ← 0
2 for p ← 1 to W
3 min ← ∞
4        for i ← 1 to size
5                  if coins[i] ≤ p then
6                         if 1 + C[p − coins[i]] < min then
7                                  min ← 1 + C[p − coins[i]]
8                                  coin ← i
9                                  fValues[p] ← min
10                       S[p] ← coin
11 return C and S

Refer to full Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

static int index=0; static int [] S = new int[W + 1]; static int[] fValues= new int[W+1] ; public void coinChange(int[] coins , int w){ if(w > W) return ; int min=w , fValue , coin = 0; for(int i=0;i<coins.length ;i++) { if(w >= coins[i]) { fValue = fValues[w-coins[i]] ; if(min > fValue) { min = fValue; coin=i; } } } fValues[++index] = min +1 ; S[w] = coin ; coinChange(coins , w + 1); } public void print(int W ){ while(W>0) { System.out.print(coins[S[W]] + "\t"); W=W-coins[S[W]]; } }

References: http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf