The missing subset sum
Here's a cute algorithmic puzzler that occurred to me yesterday, though perhaps it was long-known to others.

Let S be a set (or multiset) of positive integers. Describe an efficient algorithm for finding the smallest positive integer x such that x is not the sum of some subset of S.

Using dynamic programming to test each possible subset sum isn't good enough; I want something strongly polynomial. Or, to be really concrete about it, let's suppose that you have a computer in which W-bit integers can be added, subtracted, and compared in constant time, that additionally you have a constant time operation to compute floor(log₂(k)) for any W-bit value k, and that all the members of S are W-bit numbers and that W ≥ log₂|S|; I want an algorithm that runs in time O(|S|+W) in this model.

If you get stuck, the characterization of practical numbers might give you a hint.