Least wasteful use of stamps to achieve a given postage

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.

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).