0/1_knapsack

#include<iostream>
#include<vector>
#include<algorithm>

#define MAX 12   // Max space in bag

using namespace std;

vector<pair<int, int>> item_stack;

// vector of items -> pair(price, qty)
vector<pair<int, int>> items = {
  make_pair<int, int>(11, 2),
  make_pair<int, int>(20, 5),
  make_pair<int, int>(15, 3),
  make_pair<int, int>(13, 7),
};

// utility functions
bool item_cmp (pair<int, int>& a, pair<int, int>& b) {
  return a.first > b.first;
}

void knapsack_function(vector<pair<int, int>>& v, int bag_size) {

  for(auto& x: v) {
    if(x.second <= bag_size) {
      bag_size -= x.second;
      item_stack.push_back(x);
      knapsack_function(v, bag_size);
      break;
    }
  }
}

int main() {
  sort(items.begin(), items.end(), item_cmp);     // Sorts in descending order according to price
  knapsack_function(items, MAX);

  for(auto x: item_stack) {
    cout<<"Profit: "<<x.first<<"   "<<"Weight: "<<x.second<<endl;
  }
}