Q-19 0 - 1 Knapsack Problem | Practice | GeeksforGeeks

class Solution 
{ 
    //Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int w ,int wt[], int val[], int n) 
    { 
        // return solve(wt , val , n-1 , w , new Integer[n][w+1]);
        
        //tabulization-> n*w | sc-> n*w
        int dp[][] = new int[n][w+1];
        
        for(int i = 0 ;i < n ;i++){
            for(int j = 0 ;j < w+1 ; j++){
                if(i == 0){
                    if(j >= wt[0])
                    dp[i][j] = val[i];
                    
                    else
                    dp[i][j] = 0;
                }
                
                else{
                    int take = (int)-1e9;
                    
                    if(j - wt[i] >= 0)
                    take = val[i] + dp[i-1][j-wt[i]];
                    int notake = 0 + dp[i-1][j];
                    
                    dp[i][j] = Math.max(take , notake);
                }
            }
        }
        
        return dp[n-1][w];
    } 
    
    //Recursion -> 2*(n*w) Memo - > 2*n*w | Sc- n*w +. n*w
    static int solve(int wt[] , int val[] , int i, int w , Integer[][] dp) {
        
        if(i == 0){
            if(w >= wt[0])
            return val[i];
            
            else
            return 0;
        }
        if(dp[i][w] != null)
        return dp[i][w];
        
        //making faith calls from (n,w) to give answers 
        int take = (int)-1e9;
        
        //write out of bound conditions here and not above the base case so that
        //it is easier to copy this whole logic in tabulization
        if(w-wt[i] >=0)
        take = val[i] + solve(wt ,val , i-1 , w - wt[i] , dp);
        
        int notake = 0 + solve(wt , val , i-1 ,w , dp);
        
        return dp[i][w] = Math.max(take , notake);
    }
}