coin change problem

The problem of making a given amount of money with the fewest coins from a set of coin values.

In more detail

Greedily taking the largest coin that fits is optimal for coin systems such as 1, 5, 10 and 25, but fails for others: with coins 1, 3 and 4, greedy makes 6 as 4 + 1 + 1 while 3 + 3 uses fewer. Dynamic programming always finds the minimum. It is the course's standard warning that greedy needs proof.

Related terms

Taught in

References