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:
Post a Comment