Q23 Knapsack with Duplicate Items | Practice | GeeksforGeeks

class Solution{
    static int knapSack(int n, int w, int profit[], int wt[])
    {
        // return solve(profit , wt , n-1 , w , new Integer[n][w+1]);
        
        //tabulization 
        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){
                    dp[i][j] = (j/wt[i])*profit[i];
                }
                else{
                    int notake = 0 + dp[i-1][j];
                    int take = (int)-1e9;
                    if(j-wt[i] >= 0)
                    take = profit[i] + dp[i][j-wt[i]];
            
                    dp[i][j] = Math.max(notake , take);
                }
            }
        }
        return dp[n-1][w];
    }
    
    //Recursion-> exponential(can't determine no. of options) | 
    //Memoization -> n*amt Sc-> n*amt + amt(stack height)
    static int solve(int profit[] , int wt[] , int i , int w , Integer[][] dp){
        if(i == 0){
            // if(w < wt[i])
            // return 0;

            // else
            return (w/wt[i])*profit[i];
        }
        if(dp[i][w] != null)
        return dp[i][w];
        
        int notake = 0 + solve(profit ,wt , i-1 , w, dp);
        int take = (int)-1e9;
        if(w-wt[i] >= 0)
        take = profit[i] + solve(profit , wt , i , w-wt[i] ,dp);

        return dp[i][w] = Math.max(notake , take);
    }
}