Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
0-1 Knapsack
//g++ 7.4.0 #include <bits/stdc++.h> using namespace std; int dp[1002][1002]; int knapsack(int num[],int weight[],int n,int w) { if(n==0 || w==0) { return dp[n][w]=0; } if(dp[n][w]!=-1) { return dp[n][w]; } else if(weight[n-1]<=w) { return dp[n][w]=max(num[n-1]+knapsack(num,weight,n-1,w-weight[n-1]),knapsack(num,weight,n-1,w-weight[n-1])); } else { return dp[n][w]=knapsack(num,weight,n-1,w); } } int main() { int t; cin>>t; while(t--) { memset(dp,-1,sizeof(dp)); int n; cin>>n; int w; cin>>w; int num[n]; int weight[n]; for(int i=0;i<n;i++) { cin>>num[i]; } for(int i=0;i<n;i++) { cin>>weight[i]; } int ans=knapsack(num,weight,n,w); cout<<ans<<endl; } }
run
|
edit
|
history
|
help
0
Test 9(2021)
Inventory
runtime template mode processor
virtual function
check Prime
Hii
GCC bug #79511
Text Justification
Rezolvare
inheritance