Puzzle part 2: Meta-design

When the postage-stamp puzzle appeared on Usenet, my first thought was that a solution that contains three nested loops can't be right. Of course, that thought says little about what strategy is right. So let's think a little about how to approach the problem.

Our input is an amount of money and a collection of stamp denominations. The object of the game is to minimize the total number of stamps that we use to make up that amount of money.

Of course, there may be no solution at all. For example, if our smallest stamp is 2 cents, we have no way of making up a 1-cent sum. So whatever we do, we must take that possibility into account.

Some of the Usenet solutions I saw used a greedy algorithm: They tried to use as many 2-cent stamps as would fit, then as many 7-cent stamps, then as many 9-cent stamps. As stated, this algorithm doesn't work.

Consider, for example, what happens if you're trying to make up 11 cents. You'll take five 2-cent stamps, with one cent left over, and then you're stuck. Whereas if you had taken only one 2-cent stamp, you'd have 9 cents left over.

An obvious solution to that problem is to go the other way: Take as many 9-cent stamps as possible, then as many 7-cent, and finally as many 2-cent stamps. As it turns out, that doesn't work either. Consider, for example, what happens if you have 23 cents. You can take two 9-cent stamps, after which you have 5 cents left and you're stuck. If you had taken as many 7-cent stamps as possible first, you'd have wound up with three 7-cent stamps and one 2-cent stamp.

This line of reasoning suggests that being greedy isn't going to solve this problem. Instead, we need a systematic way of considering all possibilities. My next article will discuss one way of doing so.

Posted by Andrew Koenig at 12:00 PM  Permalink