Recursion Approach

Method 2: Memoization 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++

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

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

Recursion Approach

Approach:

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

Similar Reads