// This class illustrates techniques for calculating the number of different
// combinations of coins that can be used to reach a specific amount of money.
// In England the currency is made up of pounds, £ (dollars), and pence, p (pennies).
// There are commonly 8 types of coins in general circulation:
// 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
/**
* This is serious brute force. It's optimized a little bit because we are
* checking the limit for each coin counter.
*
*/
public class Problem031 {
private static final boolean debug = false;
public static int Solve(int pounds) {
int result = 0;
int i, j, total; // 0 1 2 3 4 5 6 7
int coins[] = new int[8]; // 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p
int coinsMax[] = new int[8]; // 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p
for (i = 0; i < 8; i++) {
coins[i] = 0;
}
coinsMax[0] = 200;
coinsMax[1] = 100;
coinsMax[2] = 40;
coinsMax[3] = 20;
coinsMax[4] = 10;
coinsMax[5] = 4;
coinsMax[6] = 2;
coinsMax[7] = 1;
try {
while (true) {
total = coins[0] * 1
+ coins[1] * 2
+ coins[2] * 5
+ coins[3] * 10
+ coins[4] * 20
+ coins[5] * 50
+ coins[6] * 100
+ coins[7] * 200;
if (total == (pounds * 100)) {
if (debug) {
for (int k = 0; k < coins.length; k++) { System.out.print(coins[k] + ", ");}
System.out.println(".");
}
result++;
}
for (i = 0; i < coins.length; i++) {
coins[i]++;
if (coins[i] > coinsMax[i]) {
if (i == coins.length - 1) {
throw new Exception("done");
}
coins[i] = 0;
} else {
break;
}
}
}
} catch (Exception ex) {
System.out.println("Solve(): + ex.");
}
return result;
}
}