We need to find the highest total value we can carry without crossing the weight limit.

Base Case: If only one item is left, take it if it fits; otherwise, take nothing.

Steps:

Skip: Leave the current item and check the best total value from the remaining ones.
Choose: Take the current item (only if it fits) and add its value to the best total from the remaining ones.
Result: Pick the option that gives the higher total value.

Using Memory to Speed Up

Make a table to store results for different weight limits and items.
Before solving again, check if the result is already in the table. If yes, use it.
If not, calculate it, store it in the table, and then return it.

Code

#include <bits/stdc++.h>
using namespace std;

// Class to solve 0/1 Knapsack using memoization
class Solution {
public:
    // Function to compute maximum value
    int knapSackUtil(int ind, int W, vector<int>& wt, 
                     vector<int>& val, vector<vector<int>>& dp) {
        // Base case: if only one item left
        if (ind == 0) {
            if (wt[0] <= W) return val[0];
            else return 0;
        }
        // If already computed return it
        if (dp[ind][W] != -1) return dp[ind][W];
        
        // Exclude current item
        int notTaken = knapSackUtil(ind - 1, W, wt, val, dp);
        
        // Include current item if possible
        int taken = INT_MIN;
        if (wt[ind] <= W) 
            taken = val[ind] + knapSackUtil(ind - 1, W - wt[ind], 
                                            wt, val, dp);
        
        // Store result in dp
        return dp[ind][W] = max(notTaken, taken);
    }

    // Main function to call
    int knapSack(int W, vector<int>