Introduction
The knapsack problem is a well-known optimization problem in computer science, specifically in the field of combinatorial optimization. It involves selecting items with certain values and weights to maximize the total value while staying within a given capacity constraint. In the 0-1 Knapsack variant, each item can only be chosen once, and it cannot be broken (0-1 property). The task is to determine the maximum value subset of items that can be put in a knapsack of capacity W.
.png)
Problem Statement
Given the weights and values of N items, represented by two integer arrays val[0..N-1] and wt[0..N-1] respectively, along with a knapsack capacity W, the goal is to find the maximum value subset of val[] such that the sum of the weights of this subset is smaller than or equal to W.
Example 1
Input:
N = 3
W = 50
values[] = {60, 100, 120}
weights[] = {10, 20, 30}
Output: 220
Example 2
Input:
N = 3
W = 2
values[] = {10, 20, 30}
weights[] = {1, 1, 1}
Output: 50
Recursive code
#include <iostream>
using namespace std;
int knapSack(int W, int wt[], int val[], int n)
{
// Base case
if (n == 0 || W == 0)
return 0;
if (wt[n-1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(val[n-1] + knapSack(W - wt[n-1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
int main() {
int val[] = {10, 20, 30};
int wt[] = {1, 1, 1};
int W = 2;
int n = 3;
cout << knapSack(W, wt, val, n);
return 0;
}
Explanation (Recursive Solution)
The recursive solution uses a function `knapSack` to solve the 0-1 Knapsack problem.
- The base case of the recursive function is when there are no items left (`n == 0`) or the knapsack capacity is zero (`W == 0`). In both cases, the maximum value that can be achieved is 0, so the function returns 0.
- If the weight of the current item (`wt[n-1]`) is greater than the current knapsack capacity (`W`), the item cannot be included in the knapsack. In this case, the function calls itself recursively, excluding the current item, and passes the same knapsack capacity and the previous item: `knapSack(W, wt, val, n - 1)`.
- If the weight of the current item is less than or equal to the current knapsack capacity, the function considers two possibilities:
- Include the current item: Add its value (`val[n-1]`) to the maximum value obtained by recursively calling the function with the reduced knapsack capacity (`W - wt[n-1]`) and the previous item: `val[n-1] + knapSack(W - wt[n-1], wt, val, n - 1)`.
- Exclude the current item: Calculate the maximum value obtained by recursively calling the
function without including the current item: `knapSack(W, wt, val, n - 1)`.
- Return the maximum value between the two possibilities obtained in step 3.
Dynamic Programming (DP) Solution
The DP solution optimizes the recursive solution by storing the computed values in a 2D array to avoid redundant calculations.
Code
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
// A utility function that returns maximum of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
vector<vector<int>> K(n + 1, vector<int>(W + 1));
// Build table K[][] in bottom-up manner
for (int i = 0; i <= n; i++)
{
for (int w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
};
int main()
{
int n, W;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter the knapsack capacity: ";
cin >> W;
int val[n];
int wt[n];
cout << "Enter the values of the elements: ";
for (int i = 0; i < n; i++)
cin >> val[i];
cout << "Enter the weights of the elements: ";
for (int i = 0; i < n; i++)
cin >> wt[i];
Solution ob;
int maxValue = ob.knapSack(W, wt, val, n);
cout << "Maximum value in the knapsack: " << maxValue << endl;
return 0;
}
Explanation
- The code defines a class `Solution` that contains the `knapSack` function to solve the 0-1 Knapsack problem.
- The function `knapSack` takes the knapsack capacity `W`, arrays of weights `wt[]` and values `val[]`, and the number of items `n` as input.
- It initializes a 2D vector `K` of size `(n + 1) x (W + 1)` to store the dynamic programming table.
- It then iterates through all possible combinations of items and capacities using nested loops.
- For each item `i` and capacity `w`, it checks if including the current item is feasible (i.e., weight of the current item is less than or equal to the capacity).
- If feasible, it takes the maximum value of either including the current item (adding its value and considering the remaining capacity) or excluding the current item.
- If not feasible, it assigns the value of the previous row for the same capacity.
- Finally, it returns the maximum value stored in `K[n][W]`, which represents the maximum value achievable using all `n` items and the total capacity `W`.
The `main` function reads the number of elements, knapsack capacity, values, and weights from the user. It creates an instance of the `Solution` class and calls the `knapSack` function, passing the input values. It then prints the maximum value that can be achieved in the knapsack.
Conclusion
The 0-1 Knapsack problem is solved using both recursive and DP approaches. The recursive solution evaluates all possible combinations of items, which results in redundant calculations and exponential time complexity. On the other hand, the DP solution optimizes the recursive approach by using a 2D array to store and reuse the computed values, reducing the time complexity to polynomial time.
In conclusion, the DP solution provides a more efficient and scalable approach to solve the 0-1 Knapsack problem, especially for large input sizes, as it avoids redundant calculations and improves the overall runtime of the algorithm.
.png&description=Solving the Knapsack Problem: Maximizing Value with Limited Capacity){kind=link}