Puzzle part 3: a design approach that works

How many 2-, 7-, and 9-cent stamps are the minimum to make up a given amount? We've seen that a greedy strategy won't solve this problem, so what can we do?

One useful way of solving problems such as this one is to do so recursively, one denomination at a time. For example, although we don't know how many 2-cent stamps are optimum, we do know the range of possible values: We can't possibly have a negative number of stamps, and if we're trying to make up n cents, we can't have more than floor(n/2) stamps.

So here's a way of solving the problem: For each value in the range [0, n/2], assume that we have that number of 2-cent stamps and ask--recursively--what is the best way of solving the remaining problem. In other words, if we're assuming k 2-cent stamps, we find the best way of making up n-k cents with only 7- and 9-cent stamps, then add k to the number of stamps in the best solution. The value of k that minimizes the sum is the key to the puzzle.

It is true that this solution might be slow in practice; but we won't know until we try it whether it's too slow to be practical. So let's think about how to write such a program and see what it does for us.

Posted by Andrew Koenig at 09:10 AM  Permalink