Maximum value of postage stamps on an envelope

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.

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.