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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.