0/1 Knapsack Problem: A Classic Example
The 0/1 Knapsack Problem is a classic problem in computer science and operations research that involves finding the optimal way to pack a set of items of different weights and values into a knapsack of limited capacity. In this article, we will explore a simple example of the 0/1 Knapsack Problem and how to solve it using dynamic programming.
The Problem Statement
Imagine you are a traveler who wants to pack a knapsack with a capacity of 10 kg for a trip. You have the following items to choose from:
| Item | Weight (kg) | Value |
|---|---|---|
| Book | 2 | 10 |
| Camera | 3 | 20 |
| Laptop | 5 | 30 |
| Shoes | 1 | 5 |
| Bike | 7 | 40 |
You want to select a subset of these items to pack in your knapsack such that the total weight of the selected items does not exceed 10 kg, and the total value of the selected items is maximized.
The 0/1 Knapsack Problem Constraints
The 0/1 Knapsack Problem has two main constraints:
- Weight constraint: The total weight of the selected items must not exceed the knapsack capacity (10 kg in this case).
- ** Binary constraint**: Each item can either be included (1) or excluded (0) from the knapsack.
Solving the Problem using Dynamic Programming
To solve this problem, we can use dynamic programming to build a 2D table that stores the maximum value that can be obtained with a given weight capacity.
Let's create a 2D table dp with dimensions (n+1) x (W+1), where n is the number of items and W is the knapsack capacity.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
| 2 | 0 | 5 | 10 | 10 | 10 | 15 | 15 | 15 | 20 | 20 | 20 |
| 3 | 0 | 5 | 10 | 15 | 20 | 25 | 25 | 30 | 35 | 35 | 40 |
| 4 | 0 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 45 |
In this table, dp[i][w] represents the maximum value that can be obtained with the first i items and a weight capacity of w.
We can fill in the table using the following recurrence relation:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
where weight[i] and value[i] are the weight and value of the i-th item, respectively.
The maximum value that can be obtained is stored in the bottom-right cell of the table, which is dp[4][10] = 45.
The Optimal Solution
To find the optimal subset of items, we can backtrack from the bottom-right cell of the table.
The optimal solution is to select the following items:
- Book (2 kg, 10 value)
- Camera (3 kg, 20 value)
- Shoes (1 kg, 5 value)
The total weight of these items is 6 kg, and the total value is 45.
Conclusion
In this article, we explored a simple example of the 0/1 Knapsack Problem and how to solve it using dynamic programming. The 0/1 Knapsack Problem is a classic problem in computer science and operations research, and it has many applications in real-world scenarios, such as resource allocation and scheduling. By using dynamic programming, we can efficiently solve this problem and find the optimal solution.
