Monday, January 28, 2013

How to count possible combination for coin problem


How to count possible combination for coin problem



/*
          Please implement this method to
          return the number of different combinations of US coins
          (penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c)
          which may be used to produce a given amount of money.
          For example, 11 cents can be produced with
          one 10-cent coin and one 1-cent coin,
          two 5-cent coins and one 1-cent coin,
          one 5-cent coin and six 1-cent coins,
          or eleven 1-cent coins.
          So there are four unique ways to produce 11 cents.
          Assume that the cents parameter is always positive.
         */

The same problem for coins(1,5,10,25,50) has one of below solutions. The solution should satisfy below equation: 1*a + 5*b + 10*c + 25*d + 50*e == cents
public static void countWaysToProduceGivenAmountOfMoney(int cents) {
    for(int a = 0;a<=cents;a++){
        for(int b = 0;b<=cents/5;b++){
            for(int c = 0;c<=cents/10;c++){
                for(int d = 0;d<=cents/25;d++){
                    for(int e = 0;e<=cents/50;e++){
                        if(1*a + 5*b + 10*c + 25*d + 50*e == cents){
                            System.out.println("1 cents :"+a+", 5 cents:"+b+", 10 cents:"+c);
                        }
                    }
                }
            }
        }
    }
}

No comments: