Algorithm for Postage Stamp Problem

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

Rather than exhaustively computing the sums of all the possible combinations of stamps (perhaps by recursion), consider all the possible sums, and work out what the smallest number of stamps is to produce each sum. There are loads of combinations of stamps, but a lot fewer distinct sums.

In the example you gave in a comment, 10 stamps fit on an envelope, and no stamp has value greater than 100. There are n^10 combinations of stamps, where n is the number of denominations of stamp available. But the greatest possible sum of 10 stamps is only 1000. Create an array up to 1001, and try to think of an efficient way to work out, for all of those values together, the least number of stamps required to make each one. Your answer is then the least index requiring 11 (or more) stamps, and you can cap each stamp-count at 11, too.

"Efficient" in this case basically means, "avoid repeating any work you don't have to". So you're going to want to re-use intermediate results as much as possible.

If that's not enough of a hint then either (a) I'm wrong about the approach (in which case sorry, I haven't actually solved the problem myself before answering) or (b) update to say how far you've got along those lines.

Answer 3

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.

Answer 4

Maybe it's a bit unhelpful to just give "hints" about a DP solution when there is speculation that one even exists. So here is runnable Perl code implementing the actual DP algorithm:

#!/usr/bin/perl
my ($n, @stamps) = @ARGV;
my @_solved;        # Will grow as necessary

# How many stamps are needed to represent a value of $v cents?
sub solve($) {
    my ($v) = @_;
    my $min = $n + 1;

    return 0 if $v == 0;

    foreach (@stamps) {
        if ($v >= $_) {
            my $try = $_solved[$v - $_] + 1;
            $min = $try if $try < $min;
        }
    }

    $_solved[$v] = $min;
    return $min;
}

my $max = (sort { $a <=> $b } @stamps)[-1];

# Main loop
for (my $i = 0; $i <= $max * $n; ++$i) {
    my $ans = solve($i);
    if ($ans > $n) {
        print "$i cannot be represented with <= $n stamps of values " . join(", ", @stamps) . ".\n";
        last;
    }
}

Ordinarily solve() would require a recursive call, but because we always try values in the order 0, 1, 2, 3..., we can just use the @_solved array directly to get the answer for smaller problem sizes.

This takes 93ms on my PC to solve the case for stamp sizes 1, 4, 12, 21 and envelope size 1000. (The answer is 20967.) A compiled language will be even faster.