The Frobenius Number

This is a set of problems that ask for this: given a set of numbers S, find the minimal number that cannot be represented using linear combination of numbers in S.

Some results are:
1) if |S| = 1, then {1} is the only solution.
2) if |S| = 2, then for S = {a, b}, solution exists iff gcd(a, b) = 1, and the solution is a*b - a - b (James Joseph Sylvester, 1884). And the number of non-representable numbers in this case is (a-1)(b-1)/2.
3) if |S| = 3, algorithm exists to calculate the solution. One example is the McNugget number: you can buy McDonald's Chicken McNuggets in the pack of 6, 9 or 20, so S = {6, 9, 20}, the Frobenius number is 43:
44 = 6 + 9 + 9 + 20
45 = 9 + 9 + 9 + 9 + 9
46 = 6 + 20 + 20
47 = 9 + 9 + 9 + 20
48 = 6 + 6 + 9 + 9 + 9 + 9
49 = 9 + 20 + 20
Any number bigger can be obtained from these by adding a multiple of 6.
4) for general cases, it is proved to be NP-hard.

See here for an introduction to the Frobenius Number problem. Here is an extension of this problem into a set of strings and solution (2007).