farhin_khaled

0/1 knapsack

Dec 1st, 2021 (edited)
399
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ull unsigned long long int
  4. #define pb push_back
  5. #define mp make_pair
  6. #define in insert
  7. #define f first
  8. #define sc second
  9. #define M 1000005
  10. #define MAX 10000000
  11. using namespace std;
  12.  
  13. int main()
  14. {
  15.   int n,sz_w;
  16.   cin >> n >> sz_w;
  17.   int wt[n],p[n];
  18.   for(int i=1;i<=n;i++) cin >> wt[i];
  19.   for(int i=1;i<=n;i++) cin >> p[i];
  20.   int k[n+2][sz_w+2];
  21.   for(int i=0;i<=n;i++)
  22.   {
  23.     for(int w=0;w<=sz_w;w++)
  24.     {
  25.       if(i==0 || w==0) k[i][w] = 0;
  26.       else if(wt[i]<=w)
  27.       k[i][w] = max(p[i]+k[i-1][w-wt[i]],k[i-1][w]);
  28.       else k[i][w] = k[i-1][w];
  29.     }
  30.   }
  31.   int temp_sz = sz_w;
  32.   for(int i=n;i>=1 && temp_sz;i--)
  33.   {
  34.     for(int w=temp_sz;w>=1 && temp_sz;w--)
  35.     {
  36.       if(k[i][w]==k[i-1][w]) continue;
  37.       else
  38.       {
  39.         w = temp_sz-wt[i];
  40.         temp_sz -= wt[i];
  41.         cout << "weight = " << wt[i] << " price = " << p[i] << endl;
  42.       }
  43.     }  
  44.   }
  45.  
  46.   cout << k[n][sz_w] << endl;
  47.  
  48.   return 0;
  49. }
  50.  
  51.  
RAW Paste Data