Least wasteful use of stamps to achieve a given postage

Question

You have sheets of $42$-cent stamps and $29$-cent stamps, but you need at least $\$3.20$ to mail a package. What is the least amount you can make with the $42$- and $29$-cent stamps that is sufficient to mail the package?

A contest problem such as this is probably most easily solved by tabulating the possible combinations, using $0$ through ceiling(total/greater value) of the greater-value stamp and computing the necessary number of the smaller stamp and the total postage involved. The particular example above would be solved with a $9$-row table, showing the minimum to be $\$3.23$, made with seven $42$-cent stamps and one $29$-cent stamp.

Is there a better algorithm for solving this kind of problem? What if you have more than two values of stamps?

Answer 1

With two stamps, you can do it in linear pseudo-linear time - O(totalCost/costOfLargerStamp) - by simply enumerating every possibility (there is only one possible count of the smaller stamp for each count of the larger stamp).

In general, however, solving this is equivalent to solving a general integer linear programming problem written in standard form, which is NP-complete.

Answer 2

Let t be your target and a and b < a be the values of the stamps you have. Let n = ⌈t/a⌉ be the maximum number of a stamps it makes sense to use.

For each number i from n to 0, consider the cost of the solution with:

• i stamps of value a and
• j = ⌈(t - i*a) / b⌉ stamps of value b

The cost of each solution would obviously be i*a + j*b.

Your solution is the pair (i, ⌈(t - i*a) / b⌉ ) that minimizes said cost. (Note there's only one unknown in that pair, i.)

An additional optimization would be to stop immediately as soon as a division without rest is performed, either when determining n or j. A division without rest means that we have found a solution that perfectly pays the due amount and cannot thus be improved on. (There may be others like it, but none that is actually better, so there's no need to keep searching).

Answer 3

It is important to understand that NP-completeness is defined in terms of input size, not in terms of either cost to be paid, C, or the number of types of stamps, S, when we are dealing with integers rather than real numbers.

This algorithm can actually be solved in time CS. We take the first stamp value an mark all multiple of it as obtainable (up to the least number greater than the cost). Then, for each subsequent stamp value, we mark as obtainable all numbers that can be obtained by adding a multiple of its value with an obtainable number (up to the least number greater than the cost). We can keep track of the lowest cost postage amount that we have found so far.

Answer 4

A similar problem is known in mathematics. It is called the "Postage-Stamp" problem, and usually asks which postal values can be realized and which cannot. Dynamic programming is a common but not polynomial-time solution for this. A polynomial time solution using continued fractions in the case of two stamp denominations exists, and more complex algorithms exist for three or more stamp denominations. Look up "Frobenius Number" for more technical information.

For the given problem, I would roughly estimate the Frobenius number, and based on the estimate make an easy guess as to a near-solution and then use a dynamic programming/tabular solution, depending on the amount of time I had to solve the problem.

Answer 5

This is a simple variation of the Knapsack problem. Which is a NP-Complete problem.

Let n to be the target value, it can be solve using knapsack's dynamic programming solutions.

If you have a finite amount of stamps, then you can add them all up, subtract the target value. Run 0-1 knapsack on the stamps with the resulting number. The stamps outside the knapsack is the solution.

If you have a infinite amount of stamps. You can either make them finite: $\lceil \frac{n}{t_i}\rceil$ stamps for stamps with value $t_i$ and run the above process, or you can compute the result by running knapsacks O(log n) times similar to a binary search.

It's no better than a naive backtracking solution when n is large. I assume you are not going to pay $100 for stamps. ;)