inhuman_Arif

0/1 knapsack

Dec 1st, 2021
674
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. int cost[100][100];
  7.  
  8. int knapsack(int n, int W, int wm[], int vm[])
  9. {
  10.     for(int i=0; i<=W; i++)
  11.         cost[0][i] = 0;
  12.  
  13.     for(int i=0; i<=n; i++)
  14.         cost[i][0] = 0;
  15.  
  16.     for(int i=1; i<=n; i++)
  17.     {
  18.         for(int j=1; j<=W; j++)
  19.         {
  20.             if(wm[i] > j)
  21.                 cost[i][j] = cost[i-1][j];
  22.             else
  23.             {
  24.                 if (vm[i]+cost[i-1][j-wm[i]] > cost[i-1][j])
  25.                     cost[i][j] = vm[i] + cost[i-1][j-wm[i]];
  26.                 else
  27.                     cost[i][j] = cost[i-1][j];
  28.             }
  29.         }
  30.     }
  31.     return cost[n][W];
  32. }
  33.  
  34. void items(int n, int W, int wm[])
  35. {
  36.     int i = n;
  37.     int j = W;
  38.  
  39.     while (i > 0 && j > 0)
  40.     {
  41.         if(cost[i][j] != cost[i-1][j])
  42.         {
  43.             printf("%d\n",i);
  44.             j-=wm[i];
  45.             i--;
  46.         }
  47.         else
  48.             i--;
  49.     }
  50. }
  51.  
  52. int main()
  53. {
  54.     #ifndef ONLINE_JUDGE
  55.         freopen("input.txt", "r", stdin);
  56.         freopen("output.txt", "w", stdout);
  57.     #endif
  58.  
  59.     int n;
  60.     cin >> n;
  61.     int wm[n+2],vm[n+2];
  62.    
  63.     wm[0]=0, vm[0]=0;
  64.     for(int i=1;i<=n;i++)
  65.         cin >> wm[i] >> vm[i];
  66.  
  67.     cout << knapsack(n, 50, wm, vm) << endl;
  68.     items(n, 50, wm);
  69.  
  70.  
  71.     return 0;
  72. }
RAW Paste Data