Making a case for Dynamic Programming: The Change Problem

Changing money greedily

Imagine that you bought an item in a bookstore for $69.24, which you paid for with $70 in cash. You’re due 76 cents in change, and the cashier now must make a decision whether to give you a fistful of 76 1-cent coins or just four coins (25 + 25 + 25 + 1 = 76). Making change in this example is easy, but it casts light on a more general problem: how can a cashier make change using the fewest number of coins?

Different currencies have different possible coin values, or denominations. In the United States, the coin denominations are (100, 50, 25, 10, 5, 1); in the ...