Coin Change — Greedy Approach

Largest-coin-first is a familiar greedy strategy, but it is optimal only for suitable coin systems. A canonical system is one in which greedy uses a minimum number of coins for every representable amount. This lesson deliberately includes both a greedy simulation and exact unbounded coin DP so students can observe failure rather than memorize an unjustified universal rule.

Prerequisites: Greedy counterexamples; integer division; basic Dynamic Programming.

Build the idea

1. Define the two procedures

   Denominations are positive integers with unlimited copies. Greedy sorts descending, takes amount/coin copies, and continues with the remainder. The DP defines dp[x] as the minimum number of coins making exactly x, with dp[0]=0 and unreachable states INF. A greedy remainder can be impossible even when another combination represents the amount.

2. See where greedy is provably safe

   For a divisibility chain such as {1,5,10}, every larger denomination is an integer multiple of the previous one. In an optimal representation, enough copies of a smaller coin to form the next larger coin can be exchanged for that one coin, reducing count. Repeated carries force the greedy quotient/remainder choices. Thus this family is canonical. Not every canonical system is a divisibility chain; this is a sufficient condition with an accessible proof.

   $$\mathrm{dp}\left[x\right]=\min \{1+\mathrm{dp}[x-c]:c\le x\}$$

3. Correctness and counterexample

   For arbitrary denominations, there is no general safe first-coin exchange. With {1,3,4} and amount 6, greedy commits to 4 then uses two ones, three coins; two threes use only two. The DP is exact: every representation of positive x ends in some coin c, leaving optimal subproblem x−c. Minimizing 1+dp[x−c] over all legal final coins covers every possibility. That proof justifies the comparison result, not the failed greedy choice.

4. Trace the implementation

   The program removes duplicate denominations after descending sorting. Greedy updates remainder and count using quotient/modulo, requiring no loop per individual coin. DP fills amounts increasingly because every positive denomination refers to a strictly smaller state. On the sample, dp[3]=1 and dp[6]≤dp[3]+1=2, beating the greedy count 3.

5. Interpret evidence correctly

   Matching greedy and DP on one amount does not prove the denomination system canonical. Conversely one disagreement disproves universal optimality. Without a coin of value 1, some amounts can be unreachable; report IMPOSSIBLE separately for each procedure. Bounded supplies, counting combinations and minimizing monetary value are different coin problems with different state transitions or objectives.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
int main(){
    int n,amount;
    std::cin>>n>>amount;
    std::vector<int>coin(n);
    for(int&x:coin){
        std::cin>>x;
    }
    std::sort(coin.begin(),coin.end(),std::greater<int>());
    coin.erase(std::unique(coin.begin(),coin.end()),coin.end());
    int remainder=amount,greedy=0;
    for(int c:coin){
        greedy+=remainder/c;
        remainder%=c;
    }
    const int INF=amount+1;
    std::vector<int>dp(amount+1,INF);
    dp[0]=0;
    for(int x=1;x<=amount;++x){
        for(int c:coin){
            if(c<=x&&dp[x-c]!=INF){
                dp[x]=std::min(dp[x],dp[x-c]+1); // Exact unbounded coin DP.
            }
        }
    }
    if(remainder){
        std::cout<<"GREEDY IMPOSSIBLE\n";
    }
    else{
        std::cout<<"GREEDY "<<greedy<<'\n';
    }
    if(dp[amount]==INF){
        std::cout<<"OPTIMAL IMPOSSIBLE\n";
    }
    else{
        std::cout<<"OPTIMAL "<<dp[amount]<<'\n';
    }
}

Complexity analysis

O(n log n) sorting and O(n) greedy simulation; exact comparison DP takes O(n·amount) time and O(amount) space. Input storage is O(n). The combined program’s cost is dominated by DP, not by the greedy simulation.

Example input and output

Read n amount (1≤n≤100, 0≤amount≤200000), then n denominations in 1..10^6, unlimited copies. Print GREEDY followed by its count or IMPOSSIBLE, and OPTIMAL followed by exact DP count or IMPOSSIBLE.

Input

3 6
1 3 4

Output

GREEDY 3
OPTIMAL 2

Greedy uses 4+1+1, while DP finds 3+3. Both represent 6 but only the second minimizes count.

Practical applications

Use greedy for systems with an appropriate correctness theorem, or as a heuristic/upper bound when failure is acceptable and stated. Use DP for exact moderate-amount arbitrary denominations. Large arbitrary amounts may require more specialized number-theory or shortest-path techniques.

Check your understanding

What does one greedy/DP disagreement prove?

Put it into practice

Try denominations {3,4} and amount 6.