coin-systems

Coin Systems

Greedy change-making algorithm for a canonical coin system. See Change-making problem — Wikipedia.

Problem

Given an amount, find the minimum number of coins needed using denominations: $2, $1, 50c, 20c, 10c, 5c, 2c, 1c.

Greedy approach

Always pick the largest coin that fits into the remaining amount. For canonical coin systems (like most real currencies) this always produces the optimal result.

This does not work for arbitrary coin denominations. For example, with coins {1, 3, 4} and amount 6, greedy picks 4+1+1 (3 coins) but the optimal is 3+3 (2 coins). Dynamic programming is needed for the general case.

Run

python coin_systems.py

Prompts for an amount in dollars and prints the breakdown.

Example

Amount: $3.87
Minimum coins: 8
  $2 × 1
  $1 × 1
  50c × 1
  20c × 1
  10c × 1
  5c × 1
  2c × 1