Monday, December 15, 2014

Coin change problem-I (Number of ways to make a change) in Java.

This is another interesting problem that can be solved using dynamic programming. In this problem we have coins of different denominations {C1, C2, C3, C4.……Cn} and an amount S, then in how many ways we can make change for S amount using n coins. For example if we have coins of denominations 1, 2, 5 then for making change for amount 6 various ways are {1,1,1,1,1,1}, {1,1,1,1,2}, {2,2,2}, {1,1,2,2}, {1,5}. So there are 4 ways to make change for amount 6 using {1,2,5} coins.

Lets say that W(i, s) be total number of ways to make change for s amount using i coins. Then W(i, s) can be expressed as:
W(i, s) = W(i-1, s) + W(i, s-c[i])

W(i-1, s) --> total number of ways to make change for s amount without using ith coin.
W(i, s-c[i]) --> all ways that include atleast one ith coin

So total number of ways is sum of 2 different sub problems thus it has optimal substructure property.

There are few boundary conditions for above function:
1. W(i, s) = 1, if i >=0 and s = 0.
if we have no amount to make change but we have coins then there is only one way which is using no coins at all.
2. W(i, s) = 0, if i = 0 and s > 0
i.e. there is an amount for making change but we have no coins to make change then there is 0 way to make change.
3. W(i, s) = W(i-1, s), if s < c[i]
 if amount s is less than value of coin than number of ways is equal to ways in which ith coin is not included.
4. W(i, s) = W(i-1, s) + W(i, s-c[i]), if i>=1 and s>=c[i]
if number of coins greater than equal to 1 and amount s greater than equal to value of coins then number of ways is sum of ways without ith coin and ways that include atleast one occurence of ith coin.

To solve this problem we can call above function recursively taking care of base cases discuss above. But in that case there are lot of repetitive recursive calls. So this problem also has overlapping sub-problems property.
Below is recursive approach without using dynamic programming.
public class CoinChange {
  
  static int numOfWaysRecursive(int [] coins, int i, int amount){
    if(amount==0){
      return 1;
    }
    if(i < 0){
      return 0;
    }
    if(amount < coins[i]){
      return numOfWaysRecursive(coins, i-1, amount);
    }else{
      return numOfWaysRecursive(coins, i-1, amount+ numOfWaysRecursive(coins, i, amount-coins[i]);
    }
  }
  
  public static void main(String[] args) {
    System.out.println("Number of ways:"+numOfWaysRecursive(new int[]{1,5,10},2,5371));
  }
}
Java2html

Number of ways:289444

We can improve performance by using bottom up dynamic programming using tabulation instead of using recursion. Below is bottom up dynamic programming solution to problem.
public class CoinChange {
  static int numOfWays(int [] coins, int amount){
    int [][] ways = new int[coins.length][amount+1];
    for (int i = 0; i < coins.length; i++) {
      ways[i][01;
    }
    for (int i = 1; i <= amount; i++) {
      ways[0][i0;
    }
    int j = 0;
    for (int i = 1; i < coins.length; i++) {
      for (j = 1; j < coins[i]; j++) {
        ways[i][j= ways[i-1][j];
      }
      for (; j <= amount; j++) {
        ways[i][j= ways[i-1][j+ ways[i][j - coins[i]];
      }
    }
    return ways[coins.length-1][amount];
  }
  
  public static void main(String[] args) {
    System.out.println("Number of ways:"+numOfWays(new int[]{0,1,5,10},5371));
  }
}
Java2html

Number of ways:289444


In above solution we are storing number of ways for each coin in 2-D array. We can optimize to use only 1-D array since every time loop runs 1-D array contain number of ways till previous coin.Memory optimize version of above solutions is:
static int numOfWays1(int [] coins, int amount){
  int [] ways = new int[amount+1];
  ways[01;
  for (int i = 0; i < coins.length; i++) {
    for (int j = coins[i]; j <= amount; j++) {
      ways[j]+=ways[j-coins[i]];
    }
  }
  return ways[amount];
}
Java2html

No comments:

Post a Comment