Coding Recipies: Greedy Algorithms

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

V₁	V₂	V₃	V₄	V₅	V₆
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:

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

       /**
  * 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

V₁	V₂	V₃
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	1	2	3	4	5
0	1	1	1	-	-
1	-	2	2	2	2
2	-	-	2	2	2
3	-	-	-	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

        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

24 Oct 2013

Coin Change Problem

Refer to full Source Code