Coin Greedy Simulator
GreedyMediumVerify local greedy choices against global optimal changes.
Alt+Shift+C
Configuration Panel
Greedy vs Optimal Comparison Audit
Greedy Coin Set Selected
-
[ ]
Optimal DP Coin Set
-
[ ]
Time Complexity
O(CoinsCount) for greedy / O(Target * CoinsCount) for DP optimal
Space Complexity
O(Target) DP memory size
Conceptual Overview
The Coin Change greedy simulator tries to solve the change problem by repeatedly choosing the largest coin denomination that fits in the remaining target amount.
Greedy Choice Property
Always choose the largest coin value <= remaining target amount. Reduce the target and repeat.
Optimal Substructure
While coin change has optimal substructure, it does NOT always satisfy the Greedy Choice Property. The greedy choice is optimal only for canonical coin systems (e.g. US coins).
Proof Idea / Correction
Counter-example proof: for coins [1, 3, 4] and target 6, greedy picks 4 + 1 + 1 (3 coins) whereas optimal is 3 + 3 (2 coins). This proves the greedy choice is locally optimal but globally suboptimal.
Source: CP-Algorithms greedy reference