Home

DP-01 Knapsack

1. include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int n,w; cin>>n>>w; int val[n],weight[n]; int i; for(i=0;i<n;i++) cin>>val[i]; for(i=0;i<n;i++) cin>>weight[i]; int a[n][w+1],j; for(i=0;i<=n;i++) a[i][0]=0; for(int i=0;i<n;i++) { for(j=1;j<=w;j++) { if(i==0) { if(j>=weight[i]) a[i][j]=val[i]; else a[i][j]=0; } else { if(j>=weight[i]) { a[i][j]=val[i]+a[i-1][j-weight[i]]>a[i-1][j]?val[i]+a[i-1][j-weight[i]]:a[i-1][j]; } else { a[i][j]=a[i-1][j]; } } } } cout<<a[n-1][w]<<endl; } return 0; }