Dynamic Programming: Knapsack Problem
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid redundant calculations, leading to more efficient solutions. One classic example of dynamic programming is the Knapsack Problem.
Knapsack Problem
The Knapsack Problem is a combinatorial optimization problem where the goal is to maximize the total value of items that can be included in a knapsack without exceeding its capacity. It can be formulated as follows:
Given n items, each with a weight wi and a value vi, and a knapsack with capacity W, find the maximum value that can be obtained by selecting a subset of the items to include in the knapsack, such that the total weight does not exceed W.
Dynamic Programming Approach
The dynamic programming approach to solve the Knapsack Problem involves constructing a table to store the maximum value that can be obtained for different capacities and subsets of items. The table is typically a two-dimensional array where rows represent the items and columns represent the capacities.
Let's denote dp[i][j] as the maximum value that can be obtained by considering the first i items and a knapsack capacity of j. The recurrence relation for filling in the table is:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])Where:
i: Index of the current item being considered.j: Knapsack capacity.w[i]: Weight of the current item.v[i]: Value of the current item.
The base cases for the recursion are when i = 0 (no items to consider) or j = 0 (knapsack capacity is zero).
Example
Consider the following items:
| Item | Weight | Value |
|---|---|---|
| 1 | 2 | 10 |
| 2 | 3 | 15 |
| 3 | 5 | 20 |
And a knapsack capacity of 7. Using dynamic programming, we can construct the following table:
| Item \ Capacity | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| 2 | 0 | 0 | 10 | 15 | 15 | 25 | 25 | 25 |
| 3 | 0 | 0 | 10 | 15 | 20 | 25 | 30 | 35 |
The maximum value that can be obtained is 35, achieved by selecting items 1 and 3.