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

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

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 2: Memoization Approach

Method 4: Space Optimized Approach

Tabulation or Bottom-up Approach

Approach:

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

Similar Reads