#include <iostream>
#include <vector>
#include <algorithm>
/*
* Function: divide_amount
* -----------------------
* 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 canonical currency systems.
*/
void divide_amount(int amount, const std::vector<int>& denom) {
std::cout << "Dividing amount: " << amount << "\n\n";
for (int d : denom) {
int count = amount / d; // how many of this denomination
if (count > 0) {
std::cout << d << "-unit: " << count << "\n";
amount %= d; // reduce remaining amount
}
}
if (amount > 0) {
std::cout << "\nWarning: leftover amount = " << amount << "\n";
}
}
int main() {
int bills_coins[9] = {500, 100, 200, 50, 20, 10, 5, 2, 1};
std::vector<int> denom(bills_coins, bills_coins + 9);
// Sort descending using std::sort and a lambda
std::sort(denom.begin(), denom.end(),
[](int a, int b) { return a > b; });
int amount = 9749;
divide_amount(amount, denom);
}
/*
run:
Dividing amount: 9749
500-unit: 19
200-unit: 1
20-unit: 2
5-unit: 1
2-unit: 2
*/
