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); } }
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