daily pastebin goal
77%
SHARE
TWEET

0-1 KnapSack

a guest Sep 18th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int maxi(int a,int b)
  4. {
  5.     return (a>b)?a:b;
  6. }
  7.  
  8. int knapsak(int w,int wt[],int val[],int n)
  9. {
  10.  
  11.     int k[n+1][w+1];
  12.     for(int i=0;i<=n;i++)
  13.     {
  14.         for(int j=0;j<=w;j++)
  15.         {
  16.             if(i==0 || j==0)
  17.             {
  18.                 k[i][j]=0;
  19.             }
  20.             else if(wt[i-1]<=j)
  21.             {
  22.                 k[i][j]=maxi(val[i-1]+k[i-1][w-wt[i-1]],k[i-1][w]);
  23.             }
  24.             else
  25.                 k[i][j]=k[i-1][w];
  26.         }
  27.     }
  28.     return k[n][w];
  29. }
  30. int main()
  31. {
  32.     int n,w;
  33.     cin >> n;
  34.     int val[n],weight[n];
  35.  
  36.     for(int i=0;i<n;i++)
  37.     {
  38.  
  39.         cin >> weight[i];
  40.         cin >> val[i];
  41.     }
  42.  
  43.     int maxW;
  44.     cin >> maxW;
  45.     cout << knapsak(maxW,weight,val,n);
  46. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top