The change-making problem asks how to make a certain sum of money using the fewest coins. With US coins {1, 5, 10, 25}
, the greedy algorithm of selecting the largest coin at each step also uses the fewest coins.
With which currencies (sets of integers including 1
) does the 'greedy' algorithm work?