## Knapsack of stamps

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)

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.