Understanding Greedy Algorithms with a Change‑Making Example in C++

Concept

Greedy algorithm makes the locally optimal choice at each step with the hope of reaching a globally optimal solution. It is applicable to many combinatorial optimization problems where a locally optimal decision leads to an overall optimum.

Algorithm Process

Formulate a mathematical model of the problem.

Decompose the model into a sequence of sub‑problems.

Solve each sub‑problem by selecting the best feasible option (local optimum).

Combine the local choices to construct a feasible solution for the original problem.

Pseudocode

solution = empty
while not reached goal:
    element = best feasible element for current state
    add element to solution
return solution

Example: Minimum Number of Banknotes

Given denominations 1, 5, 10, 50, 100 with available quantities {5, 2, 2, 3, 5}, determine the smallest number of notes needed to pay 456.

Analysis

Mathematical model : Find non‑negative integers X_i such that Σ X_i·value_i = 456 and the sum of X_i is minimized.

Greedy strategy : At each step select the largest denomination that does not exceed the remaining amount and that is still available.

Pick 100 → remaining 356

Pick 100 → remaining 256

Pick 100 → remaining 156

Pick 100 → remaining 56

Pick 50 → remaining 6

Pick 5 → remaining 1

Pick 1 → remaining 0

The greedy selection yields 7 notes: four 100‑yuan, one 50‑yuan, one 5‑yuan, and one 1‑yuan. Because the denominations are canonical, this solution is optimal.

Reference Implementation (C++)

const int N = 5;
int Count[N] = {5, 2, 2, 3, 5};   // available quantity for each denomination
int Value[N] = {1, 5, 10, 50, 100};

int solve(int money) {
    int num = 0;
    // iterate from largest to smallest denomination
    for (int i = N - 1; i >= 0; --i) {
        int use = std::min(money / Value[i], Count[i]); // maximum usable notes of this value
        money -= use * Value[i];
        num   += use;
    }
    // if money is not zero, exact payment is impossible
    if (money > 0) return -1;
    return num;
}