0-1 Knapsack Problem in C++
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 problem, each item can be either selected (1) or not selected (0), hence the name 0-1 Knapsack.
Problem Statement
Given a set of items, each with a weight w_i and a value v_i, and a knapsack with a capacity W, determine the subset of items to include in the knapsack to maximize the total value while not exceeding the knapsack capacity.
Example
Let's say we have the following items:
| Item | Weight | Value |
|---|---|---|
| A | 2 | 10 |
| B | 3 | 20 |
| C | 1 | 5 |
| D | 4 | 30 |
| E | 2 | 15 |
And the knapsack has a capacity of 7. The goal is to select a subset of items to include in the knapsack to maximize the total value while not exceeding the knapsack capacity.
Dynamic Programming Solution
The 0-1 Knapsack problem can be solved using dynamic programming. The idea is to build a 2D table dp where dp[i][w] represents the maximum value that can be obtained with i items and a knapsack capacity of w.
Here is the C++ code to solve the 0-1 Knapsack problem using dynamic programming:
#include
#include
using namespace std;
int knapsack(vector weights, vector values, int capacity) {
int n = weights.size();
vector> dp(n + 1, vector(capacity + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
int main() {
vector weights = {2, 3, 1, 4, 2};
vector values = {10, 20, 5, 30, 15};
int capacity = 7;
int max_value = knapsack(weights, values, capacity);
cout << "Maximum value: " << max_value << endl;
return 0;
}
Explanation
The knapsack function takes three inputs: weights, values, and capacity. It returns the maximum value that can be obtained with the given inputs.
The function builds a 2D table dp where dp[i][w] represents the maximum value that can be obtained with i items and a knapsack capacity of w.
The function iterates over the items and the knapsack capacity, and for each cell in the table, it checks if the current item can be included in the knapsack. If it can, it calculates the maximum value by considering two options:
- Include the current item and take the maximum value from the remaining capacity.
- Do not include the current item and take the maximum value from the previous row.
The function returns the maximum value that can be obtained with the given inputs.
Output
Running the code with the example inputs, we get:
Maximum value: 60
The maximum value that can be obtained is 60 by selecting items A, C, and E.
Time Complexity
The time complexity of the dynamic programming solution is O(nW), where n is the number of items and W is the knapsack capacity.
Space Complexity
The space complexity of the dynamic programming solution is O(nW), where n is the number of items and W is the knapsack capacity.
