0-1Knapsack.txt

#include <iostream>
using namespace std;
#include<bits/stdc++.h>
int main() 
{
  int n;
   cin>>n;
   vector<int> value(n);
   vector<int> weight(n);
   int target,a,b;
   for(int i=0;i<n;i++)
   {
       cin>>a;
       value[i]=a;
   }
   for(int i=0;i<n;i++)
   {
       cin>>b;
       weight[i]=b;
   }
   cin>>target;
   int dp[n+1][target+1];
   for(int i=0;i<=n;i++)
   {
       dp[i][0]=0;
   }
   for(int i=1;i<=target;i++)
   {
       dp[0][i]=0;
   }
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=target;j++)
       {
           if(weight[i-1]<=j)
           {
               dp[i][j]=max(value[i-1]+dp[i-1][j-weight[i-1]],dp[i-1][j]);
           }
           else
           dp[i][j]=dp[i-1][j];
       }
   }
   cout<<dp[n][target];
   return 0;

}