pompeiifreckles

0/1_knapsack

Dec 5th, 2020
857
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4.  
  5. #define MAX 12   // Max space in bag
  6.  
  7. using namespace std;
  8.  
  9. vector<pair<int, int>> item_stack;
  10.  
  11. // vector of items -> pair(price, qty)
  12. vector<pair<int, int>> items = {
  13.   make_pair<int, int>(11, 2),
  14.   make_pair<int, int>(20, 5),
  15.   make_pair<int, int>(15, 3),
  16.   make_pair<int, int>(13, 7),
  17. };
  18.  
  19. // utility functions
  20. bool item_cmp (pair<int, int>& a, pair<int, int>& b) {
  21.   return a.first > b.first;
  22. }
  23.  
  24. void knapsack_function(vector<pair<int, int>>& v, int bag_size) {
  25.  
  26.   for(auto& x: v) {
  27.     if(x.second <= bag_size) {
  28.       bag_size -= x.second;
  29.       item_stack.push_back(x);
  30.       knapsack_function(v, bag_size);
  31.       break;
  32.     }
  33.   }  
  34. }
  35.  
  36. int main() {
  37.   sort(items.begin(), items.end(), item_cmp);     // Sorts in descending order according to price
  38.   knapsack_function(items, MAX);
  39.  
  40.   for(auto x: item_stack) {
  41.     cout<<"Profit: "<<x.first<<"   "<<"Weight: "<<x.second<<endl;
  42.   }
  43. }
  44.  
RAW Paste Data