DP- KnapSacks HackerEarth

KnapSacks HackerEarth 

#include<bits/stdc++.h>

using namespace std;

#define file() freopen("in.txt","r",stdin)

#define IO ios_base::sync_with_stdio(false),cin.tie(0)

#define ll long long

int n;

int w;

int val[1005];

int wt[1005];

int sum=0;

int result()

{

for(int i=0;i<n;i++)

{

sum+=val[i];

}

vector<ll>dp(sum+1,INT_MAX);

dp[0]=0;

for(int i=0;i<n;i++)

{

for(int j=sum;j>=0;j--)

{

if(j>=val[i])

{

dp[j] = min(dp[j],wt[i]+dp[j-val[i]]);

}

}

}

for(int i=sum;;i--)

{

if(dp[i]<=w) return i;

}

}

int main()

{

// file();

scanf("%d%d",&n,&w);

for(int i=0;i<n;i++)

{

scanf("%d",&val[i]);

}

for(int i=0;i<n;i++)

{

scanf("%d",&wt[i]);

}

cout<<result()<<endl;

return 0;

}