We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
publicstaticintunboundedKnapsack(intk,List<Integer>arr){// Write your code hereintn=arr.size();int[][]mem=newint[n+1][k+1];returnunboundedKnapsack(k,arr,n,mem);}privatestaticintunboundedKnapsack(intk,List<Integer>arr,intn,int[][]mem){if(k==0||n==0)return0;if(mem[n][k]!=0)returnmem[n][k];if(arr.get(n-1)<=k)returnmem[n][k]=Math.max(arr.get(n-1)+unboundedKnapsack(k-arr.get(n-1),arr,n,mem),unboundedKnapsack(k,arr,n-1,mem));elsereturnmem[n][k]=unboundedKnapsack(k,arr,n-1,mem);}
Java bottom-up approach:
publicstaticintunboundedKnapsack(intk,List<Integer>arr){// Write your code hereintn=arr.size();int[][]mem=newint[n+1][k+1];for(inti=1;i<n+1;i++){for(intj=1;j<k+1;j++){if(arr.get(i-1)<=j){mem[i][j]=Math.max(arr.get(i-1)+mem[i][j-arr.get(i-1)],mem[i-1][j]);}else{mem[i][j]=mem[i-1][j];}}}returnmem[n][k];}
Knapsack
You are viewing a single comment's thread. Return to all comments →
Java recursion + memoization:
Java bottom-up approach: