Here's an example of the 0/1 knapsack problem:
Suppose you are a thief and you have broken into a jewelry store. You have a knapsack with a weight limit of 10 kg, and you have the option to steal the following items:
| Item | Weight (kg) | Value ($) |
|---|---|---|
| A | 3 | 8 |
| B | 1 | 10 |
| C | 2 | 15 |
| D | 5 | 25 |
| E | 4 | 12 |
Your goal is to maximize the total value of the items you steal, while ensuring that the total weight of the stolen items does not exceed 10 kg.
To solve this problem using the 0/1 knapsack problem, you could use the dynamic programming algorithm. You would create a 2D array to store the solutions to the subproblems, where the rows represent the items and the columns represent the weight limit. You would then fill in the array by computing the maximum value that can be obtained for each combination of items and weight limit.
The resulting array would look something like this:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | 0 | 0 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 |
| B | 0 | 10 | 12 | 22 | 22 | 22 | 22 | 22 | 22 | 22 | 22 |
| C | 0 | 10 | 12 | 20 | 32 | 32 | 32 | 32 | 32 | 32 | 32 |
| D | 0 | 10 | 15 | 25 | 32 | 40 | 47 | 47 | 47 | 47 | 47 |
| E | 0 | 10 | 15 | 25 | 30 | 40 | 47 | 52 | 52 | 52 | 52 |
The value in each cell represents the maximum value that can be obtained for that combination of items and weight limit. For example, the maximum value that can be obtained with items A, B, and C and a weight limit of 6 kg is 32.
The optimal solution to the problem is to steal items B, D, and E, which have a total weight of 4 kg and a total value of $30.