0-1 knapsack
Fri Feb 03 2023 07:18:26 GMT+0000 (Coordinated Universal Time)
public class ZeroOneKnapsack { public static int zerOneKnapsack(int[] val, int[] wt, int w, int i){ if(w==0 || i==0) return 0; if(wt[i-1]<=w){ int ans1= val[i-1]+zerOneKnapsack(val,wt,w-wt[i-1],i-1); int ans2= zerOneKnapsack(val,wt,w,i-1); return Math.max(ans1,ans2); } else return zerOneKnapsack(val,wt,w,i-1); } public static int memoZerOneKnapsack(int[] val, int[]wt, int w,int i, int[][] arr){ if(w==0 || i==0){ return 0; } if(arr[i][w]!=-1){ return arr[i][w]; } if(wt[i-1]<=w){ int ans1= val[i-1]+memoZerOneKnapsack(val,wt,w-wt[i-1],i-1,arr); int ans2= memoZerOneKnapsack(val,wt,w,i-1,arr); arr[i][w]= Math.max(ans1,ans2); } else { arr[i][w]= memoZerOneKnapsack(val, wt, w, i - 1, arr); } return arr[i][w]; }//all elements of table must be initialised with -1's. public static int tabZeroOneKnapsack(int[] val, int[] wt, int w){ int n= val.length; int[][] dp =new int[n+1][w+1]; for (int i = 0; i < n+1; i++) dp[i][0]=0; for(int i=0;i<w+1;i++) dp[0][i]=0; for (int i = 1; i < n+1; i++) { for (int j = 1; j < w+1; j++) { int v=val[i-1]; int weight=wt[i-1]; if(weight<=j){ int incProfit=v+dp[i-1][j-weight]; int excProfit=dp[i-1][j]; dp[i][j]=Math.max(incProfit,excProfit); } else{ dp[i][j]=dp[i-1][weight]; } } } return dp[n][w]; } public static void main(String[] args){ int[] val={15,14,10,45,30}; int[] wt={2,5,1,3,4}; int w=7; System.out.println(zerOneKnapsack(val,wt,w,val.length)); int[][] arr=new int[val.length+1][w+1]; // for memoZeroKnapsack for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { arr[i][j]=-1; } } System.out.println(memoZerOneKnapsack(val,wt,w,val.length,arr)); } }
Comments