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.
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