The postage stamp problem is a
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
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.
[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.
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.
Mathematical definition
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 ''v''
1 + ''v''
2 + ··· + ''v''
''k'' of some number ''k'' ≤ ''m'' of (not necessarily distinct) elements of ''V''.
Complexity
This problem can be solved by
brute force search or
backtracking
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
problem. If the capacity ''m'' is arbitrary, the problem is known to be
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
.
[
]
See also
* Coin problem
* Knapsack problem
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit a ...
* Subset sum problem The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' ...
References
External links
*
*
*
*
*
*
*
* {{OEIS el, A001212, Solution to the postage stamp problem with ''n'' denominations and 2 stamps
Additive number theory
Recreational mathematics
Applied mathematics
Mathematical problems