Friday, February 27, 2015

Number of ways to make changes


Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
Assume we need 25 cents, and we want to  make changes, how can we do it?

Naturally, we will think of first, get 1 quarter
1. 25cents
Since we only need 25 cents, so at most 1 1 quarter will be used. Then we will think of the next largest domination, dime
2. 10 + 10 + 5
Because we want to add up all coins to 25
Then we further split 1 10 cent to to 5
3. 10 + 5 + 5 + 5
Then we use all 5 cents
4. 5 + 5 + 5 + 5 +5

So each time we use one domination, and find next needed coins based on the cents left, and we can do it recursively.



public class RepresentCents {
 public static int makeChange(int n) {
  return ways(n, 25);
 }
 public static int ways(int n, int denom){
  int next_denom = 0;
  //find the next largest denomination
  switch(denom) {
  case 25:
   next_denom = 10;
   break;
  case 10:
   next_denom = 5;
   break;
  case 5:
   next_denom = 1;
   break;
  //after we use the smallest denomination,
  //we need to check if all coins have added up to 
  //the desired cents, if they have, return 1 way
  //otherwise return 0 ways
  case 1:
   if (n == 0)
    return 1;
   else
    return 0;
  }
  int ways = 0;
  //check all number of coins can be used in current denomination
  for (int i = 0; i * denom <= n; i++){
   ways += ways(n - i * denom, next_denom);
  }
  return ways;
 }

 public static void main(String[] args) {
  System.out.println(makeChange(30));

 }

}

No comments:

Post a Comment