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); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter