Combinatorics – Least Wasteful Use of Stamps for 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.