Minimizing the Number of Stamps Needed for Postage

Date: 11/20/2007 at 10:15:58
From: Robert
Subject: Using the minimum number of stamps for postage.

When postage rates last changed, I was left with many stamps that no
longer easily match the price of shipping. For example, let's say I
have lots of $0.31, $0.29 and $0.01 stamps and I'd like to find the
fewest stamps for any given price. 

This isn't too hard to "eyeball" for any one price, but I want to
write a program to do it. So I am looking for an algorithm or an
equation. (I'm a good programmer, it is the math that is giving me
trouble.) 

If you just divide by the biggest stamp, take the remainder and use
that, you won't necessarily get the fewest. for example $1.74 can be
made with (5 x $0.31) + (19 x $0.01), but (6 x $0.29) uses fewer stamps. 

I can write a program to come up with *every* possible way the price
could be made with the available stamps, and then find the one that
has the fewest, but that seems inelegant.

I am pretty sure that this is a variant on "The Knapsack Problem". I'm
looking into that now. If you can help I'd still appreciate it.

Date: 11/21/2007 at 10:44:43
From: Doctor Tom
Subject: Re: Using the minimum number of stamps for postage.

Hi Robert,

It's not like the "knapsack problem", but it may be just as difficult.
It's actually related to something called "the Frobenius problem", but
it's not exactly that, either.

If you have a bunch of stamp denominations, say d_1, d_2, d_3, ...,
d_n and you're trying to produce a total postage of T, you're seeking
non-negative numbers k_1, ..., k_n such that:

  k_1d_1 + k_2d_2 + ... + k_nd_n = T

and such that:

  k_1 + k_2 + ... + k_n is minimized.

This is known as an "integer programming" problem.  It's related to
"linear programming", which can be easily mechanically solved, but
when you force the results to be integers instead of real numbers, the
solution becomes intractable.

Another way to look at it is that an equation like:

  k_1d_1 + k_2d_2 + ... + k_nd_n = T

where everything is an integer is called a "Diophantine equation", and
there are mechanical ways to solve them, but the solutions you obtain
simply involve relations among some integers that are arbitrary 
constants.  You then have to search that space for the minimal 
solution that has all non-negative values.  For example, the 
Diophantine equation:

  5x - 3y = 8

has a general solution:

  x = 1 + 3k
  y = -1 + 5k

and for every integer k, the pair of formulas above will generate a
new solution, and every solution is obtained with some integer k.  The
problem is that k may be any size, positive or negative (or zero), and
you need to search for situations where x and y are positive.  In 
this case, any k that is 1 or larger gives a valid solution.

If you have something like:

  5x + 3y = 10000000

there are only a finite number of x's and y's that work, but a large
number of them.

With more than two variables, there will be more than one constant k
in the general solution.

You'll learn a lot of interesting math if you look into this problem
carefully, but you probably won't find a good solution to your
particular problem.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/21/2007 at 11:01:47
From: Robert
Subject: Thank you (Using the minimum number of stamps for postage.)

Thank you so much for your help.  I have decided that the general case
is pretty ugly, but I may be able to build a table of stamps for
prices from $0.01 to $10.00 in a reasonable amount of time.  I'm
thinking of something like the sieve used for building a table of
primes.  It is still tricky, but now I have an expert telling me it is
tricky. :-)

Thank you again.

   Robert