Space Optimized Approach

Method 3: Tabulation or Bottom-up 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++

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

C++ Program to Solve the 0-1 Knapsack Problem

Prerequisite: Introduction to Knapsack Problem, its Types and How to solve them

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

Tags:

#CPP-DSA #C++ #C++ Programs #CPP

Method 3: Tabulation or Bottom-up Approach

Space Optimized Approach

Approach:

C++ Program to Solve the 0-1 Knapsack Problem

Similar Reads