C++ Program to Solve the 0-1 Knapsack Problem
The 0-1 Knapsack Problem is a classic problem in dynamic programming. For a given set of N items, each having a weight and a value, and a knapsack (a bag that can hold at most W weight inside it) with a maximum weight capacity W. The task is to determine the maximum sum of value of items that can be packed into the knapsack without exceeding its capacity. Unlike the Fractional Knapsack Problem, where you can take fractions of items, in the 0-1 Knapsack Problem, you can either take an item completely or leave it.
Example:
Input:
Number of Items (N): 4
Knapsack Capacity (W): 5
Item Weights: [1, 2, 4, 5]
Item Values: [5, 4, 8, 6]
Output:
13
Explanation: The optimal selection is to take the items with weights 1 and 4, giving a total value of 5 + 8 = 13.
This is the maximum value that can be achieved without exceeding the knapsack capacity of 5.
To learn more about the 0-1 Knapsack Problem refer: 0/1 Knapsack Problem
Table of Content
- Method 1: Recursion Approach
- Method 2: Memoization Approach
- Method 3: Tabulation or Bottom-up Approach
- Method 4: Space Optimized Approach
Method 1: Recursion Approach
The recursive approach explores all possible combinations of items by including or excluding each item at every step and calculating the total weight and value of all subsets (by considering only the subsets that have total weight less than W). Among all these subsets, pick the subset with maximum value. To implement this idea follow the below approach:
Approach:
- Base Case: If no items are left or the capacity is 0, return 0.
- Including the Nth item: Calculate the value if the Nth item is included, i.e., value of the Nth item plus the maximum value obtained from the remaining items and remaining weight.
- Excluding the Nth item: Calculate the maximum value obtained by the N-1 items and the original weight.
- Return the maximum of the above two cases.
- If the weight of the Nth item is greater than W, then the Nth item cannot be included and only Case 2 is possible.
The below program demonstrates the implementation of the above recursive approach:
// C++ program for solving 0/1 Knapsack Problem using
// recursion
#include <iostream>
#include <vector>
using namespace std;
// Recursive function to solve 0/1 Knapsack problem
int knapsackRecursive(vector<int>& weight,
vector<int>& value, int W, int n)
{
// Base case: no items left or capacity is 0
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more than knapsack
// capacity W, it cannot be included
if (weight[n - 1] > W)
return knapsackRecursive(weight, value, W, n - 1);
// Return the maximum of two cases: (1) nth item
// included (2) not included
return max(value[n - 1]
+ knapsackRecursive(weight, value,
W - weight[n - 1],
n - 1),
knapsackRecursive(weight, value, W, n - 1));
}
int main()
{
// define a vector of weight
vector<int> weight = { 1, 2, 4, 5 };
// define a vector of value
vector<int> value = { 5, 4, 8, 6 };
// Knapsack capacity
int W = 5;
// call the recusrsive function and print the max value
// obtained
cout << "Maximum value = "
<< knapsackRecursive(weight, value, W,
weight.size())
<< endl;
return 0;
}
Output
Maximum value = 13
Time Complexity: O(2^N), due to the exponential number of subproblems generated.
Auxilliary Space: O(N), due to the recursion stack.
Method 2: Memoization Approach
For optimizing the recursive approach discussed earlier, memoization technique can be used that stores the results of already computed subproblems to avoid redundant computations and when the same inputs occur again it returns the stored result only. To implement this idea follow the below approach:
Approach:
- First, create a 2D array of size (N+1) x (W+1) and initialize it with -1 call it “memo table”.
- Base Case: If no items are left or capacity is 0, return 0.
- Check the memo table for the inputs if the corresponding result is already computed, return it.
- Include the Nth item: calculate the value if the Nth item is included.
- Exclude the Nth item: calculate the maximum value if the Nth item is excluded.
- Store the result in the memo table and return it.
- If the weight of the Nth item is greater than W, then the Nth item cannot be included and only exclusion case is possible.
The below program demonstrates the implementation of the memorization approach:
// C++ program for solving 0/1 Knapsack Problem using
// memoization technique
#include <iostream>
#include <vector>
using namespace std;
// Function to solve 0/1 Knapsack problem using Memoization
int knapsackMemoization(vector<int>& weight,
vector<int>& value, int W, int n,
vector<vector<int> >& memo)
{
// Base case: no items left or capacity is 0
if (n == 0 || W == 0)
return 0;
// Check if the result is already in the memo table
if (memo[n][W] != -1)
return memo[n][W];
// If weight of the nth item is more than knapsack
// capacity W, it cannot be included
if (weight[n - 1] > W) {
memo[n][W] = knapsackMemoization(weight, value, W,
n - 1, memo);
return memo[n][W];
}
// Return the maximum of two cases: (1) nth item
// included (2) not included
memo[n][W] = max(
value[n - 1]
+ knapsackMemoization(weight, value,
W - weight[n - 1], n - 1,
memo),
knapsackMemoization(weight, value, W, n - 1, memo));
return memo[n][W];
}
int main()
{
// define a vector of weight
vector<int> weight = { 1, 2, 4, 5 };
// define a vector of value
vector<int> value = { 5, 4, 8, 6 };
// Knapsack capacity
int W = 5;
int n = weight.size();
// declare a 2D array of size (N+1) x (W+1) callede memo
// initialized with -1
vector<vector<int> > memo(n + 1,
vector<int>(W + 1, -1));
// call the function and print the max value
// obtained
cout << "Maximum value = "
<< knapsackMemoization(weight, value, W, n, memo)
<< endl;
return 0;
}
Output
Maximum value = 13
Time Complexity: O(N * W), due to the memoization of previously calculated subproblems.
Auxilliary Space: O(N * W), for the dp array.
Method 3: Tabulation or Bottom-up Approach
The tabulation approach, also known as bottom-up approach solves the problem iteratively by filling up a table (2D array) in a bottom-up manner. It avoids the overhead of recursive calls and is generally more space-efficient.
Approach:
- Create a 2D array dp of size (N+1) x (W+1) initialized to 0.
- Iterate through each item and each capacity from 0 to W.
- For each item and capacity, decide whether to include or exclude the item if the item can be included, update the dp table with the maximum value by including or excluding the item.
- The value in dp[N][W] will be the maximum value for the given knapsack capacity.
The below program demonstrates the implementation of the tabulation or bottom-up approach:
// C++ program for solving 0/1 Knapsack Problem using
// tabulation or bottom-up approach
#include <iostream>
#include <vector>
using namespace std;
// Function to solve 0/1 Knapsack problem using Bottom-up
// approach
int knapsackBottomUp(vector<int>& weight,
vector<int>& value, int W)
{
int N = weight.size();
// Create a 2D vector to store the maximum value that
// can be obtained dp[i][w] represents the maximum value
// that can be obtained with the first i items and
// capacity w
vector<vector<int> > dp(N + 1, vector<int>(W + 1, 0));
// Iterate over each item
for (int i = 1; i <= N; ++i) {
// Iterate over each capacity from 1 to W
for (int w = 1; w <= W; ++w) {
// Check if the weight of the current item is
// less than or equal to the current capacity
if (weight[i - 1] <= w) {
// Max value by including the current item
// or excluding it
dp[i][w] = max(dp[i - 1][w],
dp[i - 1][w - weight[i - 1]]
+ value[i - 1]);
}
else {
// If current item's weight is more than the
// current capacity, exclude it
dp[i][w] = dp[i - 1][w];
}
}
}
// Return the maximum value that can be obtained with
// the given capacity W
return dp[N][W];
}
int main()
{
// Define a vector of weights
vector<int> weight = { 1, 2, 4, 5 };
// Define a vector of values
vector<int> value = { 5, 4, 8, 6 };
// Knapsack capacity
int W = 5;
// Call the function and print the maximum value
// obtained
cout << "Maximum value = "
<< knapsackBottomUp(weight, value, W) << endl;
return 0;
}
Output
Maximum value = 13
Time Complexity: O(N * W) due to the nested loops iterating over all items and capacities.
Auxilliary Space: O(N * W)
Method 4: Space Optimized Approach
The space optimization approach reduces the space complexity of the tabulation approach by using only a single row to store intermediate results that is by using 1D array. This optimization is possible because we only need the current and previous states to compute the solution.
Approach:
- Create a 1D array dp of size (W+1) initialized to 0.
- For each item, iterate through all capacities from W to the item’s weight.
- Update the DP array with the maximum value by including the item.
- The value at dp[W] is the maximum value for the given knapsack capacity.
The below program demonstrates the implementation of the space optimized approach:
// C++ program for solving 0/1 Knapsack Problem using
// space optimized approach
#include <iostream>
#include <vector>
using namespace std;
// Function to solve 0/1 Knapsack problem with optimized
// space
int knapsackOptimized(vector<int>& weight,
vector<int>& value, int W)
{
int N = weight.size();
// Create a 1D vector to store the maximum value that
// can be obtained for each weight capacity
vector<int> dp(W + 1, 0);
// Iterate over each item
for (int i = 0; i < N; ++i) {
// Iterate over each capacity from W to the weight
// of the current item in reverse order
for (int w = W; w >= weight[i]; --w) {
// Update the dp array with the maximum value by
// including the current item
dp[w]
= max(dp[w], dp[w - weight[i]] + value[i]);
}
}
// Return the maximum value that can be obtained with
// the given capacity W
return dp[W];
}
int main()
{
// Define a vector of weights
vector<int> weight = { 1, 2, 4, 5 };
// Define a vector of values
vector<int> value = { 5, 4, 8, 6 };
// Knapsack capacity
int W = 5;
// Call the function and print the maximum value
// obtained
cout << "Maximum value = "
<< knapsackOptimized(weight, value, W) << endl;
return 0;
}
Output
Maximum value = 13
Time Complexity: O(N * W), due to the nested loops iterating over all items and capacities.
Auxiliary Space: O(W) for the dp array.