Maximum value of postage stamps on an envelope

Question

The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values.

For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

Is there an algorithm that given the maximum amount of stamps allowed and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope?

Another example:
Maximum of 5 stamps can be used
Valued: 1, 4, 12, 21
The smallest value that cannot be reached is 72. Values 1-71 can be created with a certain combination.

In the end I will probably be using Java to code this.

Answer 1

Yes, there is such an algorithm. Naively: starting with 1, try every possible combination of stamps until we find a combination that yields a sum of 1, then try for 2, and so on. Your algorithm finishes when it finds a number such that no combination of stamps adds to that number.

Albeit possibly slow, for small enough problems (say 100 stamps, 10 positions) you can solve this in a "reasonable" amount of time...

But, for large problems, ones where we have many stamps available (say 1000s) and many possible positions (say 1000s), this algorithm might take an intractable amount of time. That is, for very large problems, the time to solve the problem using this approach might be say, the lifetime of the universe, and thus it's not really useful to you.

If you have really large problems you need to find ways to speed up your search, these speedups are called heuristics. You can't beat the problem, but you can possibly solve the problem faster than the naive approach by applying some sort of domain knowledge.

A simple way to improve this naive approach might be that any time you try a combination of stamps that doesn't equal the number you're looking for you remove that combination from the possible set to try for any future number, and mark that future number as unavailable. Said another way: keep a list of numbers you've found already and the combinations that got you there, then don't look for those numbers or their combinations again.

Answer 2

Here is another tip: Every set of stamps that adds up to some given number can be formed by adding 1 stamp to a minimum-sized set of stamps that adds up to less than that number.

For example, suppose we have the stamps 1, 2, 7, 12, and 50, and a limit of 5 stamps, and we want to find out whether 82 can be represented. To get that 82, you must add either:

• A 1 to a set of stamps adding up to 82-1=81, or
• A 2 to a set of stamps adding up to 82-2=80, or
• A 7 to a set of stamps adding up to 82-7=75, or
• A 12 to a set of stamps adding up to 82-12=70, or
• A 50 to a set of stamps adding up to 82-50=32.

Those are the only possible ways that 82 can be formed. Among all those 5 possibilities, one (or possibly more than one) will have the minimum number of stamps. If that minimum number is > 5, then 82 can't be represented with stamps.

Notice also that if a number can be represented, you need to record the minimum number of stamps needed for it so that calculations for higher numbers can use it.

This, plus Steve Jessop's answer, will hopefully get your mind on the right track for a dynamic programming solution... If you're still stumped, let me know.