The postage stamp problem (also called the Frobenius Coin Problem and the Chicken McNugget Theorem [1]) 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.
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.
Mathematically, the problem can be formulated as follows: 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.