Postage stamp problem
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 latter 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.
Mathematically, the problem can be formulated as follows:
- Given an integer m and a set V of positive integers, find the smallest integer z that cannot be written as the sum v1 + v2 + ··· + vk of some number k ≤ m of (not necessarily distinct) elements of V.
This problem can be solved by brute force search or backtracking with maximum time proportional to |V|m, where |V| is the number of distinct stamp values allowed. Therefore, if the capacity of the envelope m is fixed, it is a polynomial time problem. If the capacity m is arbitrary, the problem is known to be NP-hard.
- Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30.
- Lunnon, W. F. (1969). "A postage stamp problem". Comput. J. 12 (4). pp. 377–380. doi:10.1093/comjnl/12.4.377.
- Alter, R.; Barnett, J. A. (1980). "A postage stamp problem". Amer. Math. Monthly 87: 206–210.
- Graham, R. L.; Sloane, N. J. A. (1980). "On additive bases and harmonious graphs". SIAM J. Algebr. Discr. Methods 1: 382–404. doi:10.1137/0601045.
- Challis, M. F. (1993). "Two new techniques for computing extermal h-bases A_k". Comput. J. 36 (2): 117–126. doi:10.1093/comjnl/36.2.117.
- Kohonen, J.; Corander, J. (2013). "Addtition chains meet postage stamps: reducing the number of multiplications". arXiv:1310.7090.
- Kohonen, Jukka (2014). "A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases". arXiv:1403.5945.
- Weisstein, Eric W., "Postage Stamp Problem", MathWorld.