Advertisement
Zinak

0-1 knapsack

Jul 27th, 2019
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int ks(int c,int wt[],int val[],int n)
  4. {
  5.    int i, w;
  6.    int v[n+5][c+5];
  7.  
  8.    for (i = 0; i <= n; i++)
  9.    {
  10.        for (w = 0; w <= c; w++)
  11.        {
  12.            if (i==0 || w==0)
  13.                v[i][w] = 0;
  14.            else if (wt[i] > w)
  15.                  v[i][w] = v[i-1][w];
  16.            else
  17.             v[i][w] = max(v[i-1][w],val[i-1] + v[i-1][w-wt[i-1]]);
  18.  
  19.        }
  20.    }
  21.  
  22.    return v[n][c];
  23. }
  24.  
  25. int main()
  26. {
  27.     int val[5],wt[5],n,ans;
  28.     int c;
  29.     cin>>c;
  30.     for(int i=0;i<3;i++)
  31.         cin>>val[i];
  32.     for(int i=0;i<3;i++)
  33.         cin>>wt[i];
  34.         n=sizeof(val)/sizeof(val[0]);
  35.         ans=ks(c,wt,val,n);
  36.         cout<<ans<<endl;
  37.         return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement