The knapsack algorithm involves selecting a subset of items from a given set, with each item having a weight and a value, such that the total weight of the selected items does not exceed a given capacity, and the total value of the selected items is maximized. The algorithm can be solved using dynamic programming, where the subproblems involve choosing between adding an item or skipping it, and the optimal solution can be obtained by iteratively building up a table of subproblems and their solutions.

Time Complexity: O(nlogn)

            vector<vector<int> mem;

              int knapSack(vector<int> &values, vector<int> &weights, int weight, int index)
              {
                  if (weight == 0 || index == -1)
                  {
                      return 0;
                  }
              
                  if (mem.at(index).at(weight) != -1)
                  {
                      return mem.at(index).at(weight);
                  }
              
                  if (weights.at(index) <= weight)
                  {
                      int ans = max(values.at(index) + knapSack(values, weights, weight - weights.at(index), index - 1), knapSack(values, weights, weight, index - 1));
                      mem.at(index).at(weight) = ans;
                      return ans;
                  }
                  else
                  {
                      int ans = knapSack(values, weights, weight, index - 1);
                      mem.at(index).at(weight) = ans;
                      return ans;
                  }
              }
              
              int main()
              {
              
                  vector<int> values = {60, 100, 120};
                  vector<int> weights = {10, 20, 30};
              
                  int maxWeight = 50;
              
                  vector<int> temp;
                  temp.resize(maxWeight, -1);
                  mem.resize(values.size(), temp);
              
                  cout << "MAX VALUE: " << knapSack(values, weights, maxWeight, values.size() - 1) << endl;
              }