Using only postage stamps of value 64 and 55, how can I work out the way to get closest to a high parcel value?

Question

Searching has shown many questions like this for values of 4 and 7 cents, but nothing for higher values.

For British postage, first class stamps are £0.64 and second class are £0.55. Low value stamps are available in almost any value.

A common light parcel costs £3.35, so the easiest way I can work out is (5*first class+£0.15 in low value stamps) or (1*first class+5*second class and overpay by £0.04).

I'm working out on paper the best way to reach common parcel prices, but the system I've come up with is pretty messy, and I'm sure there must be a better system.

Any advice appreciated.

Answer 1

apply the euclidean algorithm to find a lineal combination of $64$ and $55$ that gives $1$ as follows:

$64=55+9$

$55=9\cdot6+1$

From here deduce $1=55-9(6)=55-6(64-55)=7\cdot55-6\cdot64$.

Multiplying by $335$ yields:

$335=2345\cdot55-2010\cdot64$.

Now we just have to find a combination where the two coefficients are positive. Notice $-64\cdot55+55\cdot64=0$, Notice $\lfloor 2345/64 \rfloor=36$.

So $36(-64\cdot55+55\cdot64)=0=-2304\cdot55+1980\cdot64$.

Therefore $335=(2345-2304)\cdot55+(1980-2010)64=41\cdot55-30\cdot64$.

Now, it is not hard to prove if $a,b$ are coprime and $N$ is an integer then there is a unique solution $x,y$ so that $xa+yb=N$ and $x\in\{0,1,2,3\dots b-1\},y\in \mathbb Z$. (in our case $b=64$

So it is impossible to get exactly $335$.

We now obtain good lineal combinations for the next numbers, using the fact $1=7\cdot55-6\cdot64$ and $335=41\cdot55-30\cdot64$:

Notice $336=48\cdot55-36\cdot64$ (impossible)

$337=55\cdot55-42\cdot64$ (impossible)

$338=62\cdot55-48\cdot 64$ (impossible)

$339=69\cdot55-54\cdot 64 = (69-64)55 + (55-54)64=5\cdot55+64$ (possible).

If we want to use low value stamps:

$334=34\cdot55-24\cdot64$ (impossible)

$333=27\cdot55-18\cdot64$ (impossible)

$332=20\cdot55-12\cdot64$ (impossible)

$331=13\cdot55-6\cdot64$ (impossible)

$330=6\cdot55$ (possible).

So the best options are $6$ second class and $4$ cents in low value stamps, or $5$ second value stamps and $1$ first value stamp but you overpay $4$ cents.

Answer 2

Are you trying to minimize the number of stamps on the parcel, because otherwise the best solution is to simply use (in USD) 1 cent stamps and cover the entire package in postage. :)

My idea (can't prove it's rigorous) is to simply divide the total required postage by the highest stamp value you have, and take the floor (ignore remainder) of that. Then repeat with the next highest stamp value and so on. This would be trivial to implement in a computer. Actually, it would be trivial to implement in Excel or other spreadsheet program.

Example:

Given a set of postage values in monotonically decreasing order: $\lbrace p_N, p_{N-1}, p_{N-2}, ... p_2, p_1\rbrace$

Given desired total postage value of $P_{total}$.

The required number of each stamp will be a list: $\lbrace n_{N}, n_{N-1}, n_{N-2}, ... n_2, n_1\rbrace$

where: $$n_N = \left \lfloor {P_{total}\over{p_N}} \right\rfloor$$ $$n_{N-1} = \left \lfloor {{P_{total}-n_N*p_N}\over{p_{N-1}}} \right\rfloor$$ $$n_{N-2} = \left \lfloor {{P_{total}-n_N*p_N-n_{N-1}*p_{N_1}}\over{p_{N-2}}} \right\rfloor$$ and so on except for the last one: $$n_{1} = \left \lceil{{P_{total}-n_N*p_N-...-n_2*p_2}\over{p_1}} \right\rceil$$ The last one has to be a ceiling function (always up to next integer) so that you don't underpay.