import java.util.Arrays;
public class Main {
/**
* Function: divideAmount
* ----------------------
* Given an amount and a list of bills/coins, prints how many
* of each denomination are needed using a greedy algorithm.
*
* The greedy method is optimal for standard currency systems.
*/
public static void divideAmount(int amount, int[] denominations) {
System.out.println("Dividing amount: " + amount + "\n");
for (int d : denominations) {
int count = amount / d; // how many of this denomination
if (count > 0) {
System.out.println(d + "-unit: " + count);
amount %= d; // reduce remaining amount
}
}
if (amount > 0) {
System.out.println("\nWarning: leftover amount = " + amount);
}
}
public static void main(String[] args) {
int[] bills_coins = {500, 100, 200, 50, 20, 10, 5, 2, 1};
// Java: sort descending using Arrays.sort + reverse
Arrays.sort(bills_coins);
for (int i = 0; i < bills_coins.length / 2; i++) {
int temp = bills_coins[i];
bills_coins[i] = bills_coins[bills_coins.length - 1 - i];
bills_coins[bills_coins.length - 1 - i] = temp;
}
int amount = 9749;
divideAmount(amount, bills_coins);
}
}
/*
run:
Dividing amount: 9749
500-unit: 19
200-unit: 1
20-unit: 2
5-unit: 1
2-unit: 2
*/
