knapsack 0/1

knapsack.cpp

#include<bits/stdc++.h>
using namespace std;

int dp[1001][1001];
int knapsack(int val[] , int wt[] , int n , int w){
    if(dp[n][w]!=-1){
        return dp[n][w];
    }
    
    if(n==0 || w == 0){
        return 0;
    }
    
    if(wt[n-1]<=w){
        return dp[n][w] = max (val[n-1]+knapsack(val , wt , n-1 , w-wt[n-1]) , knapsack(val , wt , n-1,w));
    }
    else{
        return dp[n][w] = knapsack(val , wt , n-1 , w);
    }
}

int main() {
    memset(dp , -1 , sizeof(dp));
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int w;
	    cin>>w;
	    int val[n];
	    int wt[n];
	    for(int i = 0 ; i<n ; i++){
	        cin>>val[i];
	    }
	    for(int i = 0 ; i<n ; i++){
	        cin>>wt[i];
	    }
	    int ans = knapsack(val , wt , n , w);
	    cout<<ans<<"\n";
	}
	return 0;
}


=============================================================================================================================
	#include<bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int w;
	    cin>>w;
	    int dp[n+1][w+1];
        int val[n];
	    for(int i  = 0 ; i<n ; i++){
	        cin>>val[i];
	    }
	    int wt[n];
	    for(int i = 0 ; i<n ; i++){
	        cin>>wt[i];
	    }
	    
	    for(int i = 0 ; i<=n ; i++){
	        for(int j = 0 ; j<=w ; j++){
	            if(i==0 || j ==0)
	            dp[i][j] = 0;
	        }
	    }
	    
	    for(int i = 1 ; i<=n ; i++){
	        for(int j = 1 ; j<=w ; j++){
	            if(wt[i-1]<=j){
	                dp[i][j] = max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j]);
	            }
	            else{
	                dp[i][j] = dp[i-1][j];
	            }
	        }
	    }
	    cout<< dp[n][w]<<'\n';
	    
	}
	return 0;
}