0/1 Knapsack is a wonderful little problem, especially with its dynamic programming solution.

Now I may be mistaken but when I learned about 0/1 Knapsack three decades ago, my immediate thought was that for quite some cases you could do, using dynamic programming, an approximate version (requiring less memory and hence well, for example fitting into memory) and prove that your solution was "at most 1% off of the optimal solution". Never really looked into it though so I may have be wrong.