# Thread: Postage Stamp Problem - Maximum amount of stamps

1. ## Postage Stamp Problem - Maximum amount of stamps

The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values.

For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

Is there an algorithm that given the maximum amount of stamps and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope?

Another example:
Maximum of 5 stamps can be used
Valued: 1, 4, 12, 21
The smallest value that cannot be reached is 72. Values 1-71 can be created with a certain combination.

2. Originally Posted by Celcius
The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values.

For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

Is there an algorithm that given the maximum amount of stamps and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope?

Another example:
Maximum of 5 stamps can be used
Valued: 1, 4, 12, 21
The smallest value that cannot be reached is 72. Values 1-71 can be created with a certain combination.
For relatively small values, brute force works just fine. Can be implemented recursively. Suppose the max number of stamps is m, and there are n distinct face values. If n^m is about 10^8 or less, naive brute force will be fast enough, and as long as the face values aren't extremely large memory will also not be a problem. Since a+b is the same as b+a, we can restrict to sequences in which terms are (weakly) increasing.

Edit: Perhaps it's better to use (n+1)^m for thinking of upper bounds on time/memory.

3. An alternative approach could be constructing a table T of breadth m+1 . For every number i, let T[i][j] consist of boolean value "true" if i can be expressed as the sum of exactly m numbers, not necessarily distinct, from the set of n face-values provided, and "false" otherwise.

Let the given face values be : $k_1, k_2, ...., k_n$

It is easy to see that T[0][0] = true, and T[0][j] = false for all other j. Also, for all other i, T[i][0] = false. These are our base cases. For all other i and j, we will use the formula that we derive next.

If it is possible to represent a number at all with the given face values, then the representation will consist of at least one of those n face values. So, the truth value in T[i][j] will be $T[i-k_1][j-1] \cup T[i-k_2][j-1] \cup .... \cup T[i-k_n][j-1]$ .

To check whether a number i is representable as a sum of the given face values, we just have to check whether $T[i][0] \cup T[i][1] \cup .... \cup T[i][m]$ is true or not. Here we spend O(nm) time for each number, until we reach the smallest number not representable in the required way, at which point we terminate our algorithm.