A thief has a knapsack of a certain capacity. He looks around and sees different items of different weights and values. He would like the items he chooses for his knapsack to have the greatest value possible yet still fit in his knapsack. The problem is called the 0-1 Knapsack Problem because the thief can either take (1) or leave (0) each item.
Formal Description
Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible.
The 0/1 knapsack problem restricts the number of each items to zero or one.