The 0-1 knapsack problem is the following. A thief robbing a store finds n items. The ith item is worth vi dollars and weighs wi pounds, where vi and wi are integers. The thief wants to take as valuable a load as possible, but he can carry at most W pounds in his knapsack, for some integer W . Which items should he take?