Frabjous Times

Yesterday I spent some quality time stuffing envelopes for my new business and I happened to run across the familiar old knapsack (or subset sum) problem:

Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible. The name derives from the scenario of choosing treasures to stuff into your knapsack, when you can only carry so much weight.

In my case, the treasures are stamps of various denominations and the knapsack is the $0.37 First Class postage for my promotional mailing. I came up with these

• $0.23 (George Washington) + $0.10 (Red Cloud) + $0.04 (Father Flanagan)
• $0.29 (Grace Kelly) + 2 x $0.04 (Father Flanagan)
• $0.34 (Peaches) + 3 x $0.01 (American Kestrel)
• $0.20 (?) + $0.15 (Everett Dirksen) + 2 x $0.01 (American Kestrel)
• $0.37 (Egret)
• $0.23 (George Washington) + $0.15 (Special Olympics)

Yes, that last one breaks the knapsack and is automatically suspicious in these times, but it doesn't go over by much, and I do have lots of those $0.15 stamps in different designs for a reason I'll tell you. I rejected the combination of 2 x $0.15 (Everett Dirksen) + $0.04 (Father Flanagan) + 3 x $0.01 (American Kestrel) because when you put that many stamps on an envelope, it looks like the sender is deranged or terroristic or something.

The reason I was doing all this is my theory that junk mail which arrives with an actual stamp on it is more likely to be opened than junk mail which is metered, especially if the stamps are old and colorful. Plus, it turns out you can buy mint US stamps at eBay mint under face value for some reason I haven't figured out yet, so it's actually economical in terms of dollars and cents, not so much in terms of my time.