Question

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?

Answer 1

Step by step Explanation:

Based on what we could deduce from the above statement, the items he should take are:

• must either take one single item or must leave the other behind,
• and only a whole amount of an item must be taken,
• in which an item cannot be taken more than once into his knapsack.

Hence, the thief needs to carefully determine items with an optimal value which still falls within his specified weight (W).