I am trying to solve 0/1 Knapsack problem recursively but below code doesn't work due exponential time-complexity but yields correct answer for below test case
int capacity = 1000;
int[] weights = {123, 456, 678, 908, 145, 657, 376, 892, 708, 224, 674, 235, 671, 443, 777, 333, 999, 111, 345, 567, 234, 876};
int[] values = {543, 133, 543, 555, 567, 223, 445, 564, 456, 243, 567, 323, 465, 344, 355, 123, 344, 234, 455, 123, 456, 237};
correct_ans = 2255 my_ans = 2245
public static int helper(int capacity, int[] weights, int[] values, int curWeight, int curVal, int idx) {
if (curWeight > capacity) return 0;
if (idx == weights.length) return curVal;
int ans1 = helper(capacity, weights, values, curWeight + weights[idx], curVal + values[idx], idx + 1);
int ans2 = helper(capacity, weights, values, curWeight, curVal, idx + 1);
return Math.max(ans1, ans2);
}
public static int findMaxKnapsackProfit(int capacity, int[] weights, int[] values) {
return helper(capacity, weights, values, 0, 0, 0);
}
But when I introduce a dp matrix, it no longer works. I have seen solutions online but they mostly solve by reducing capacity whereas I am working with increasing capacity in the code below. My hypothesis is since DP enhances efficiency by storing the computations and if I store computations of above recursive code in dp matrix it should yield me the same answer only with reduced computations.
public static int helper(int capacity, int[] weights, int[] values, int[][] dp, int curWeight, int curVal, int idx) {
if (curWeight > capacity) return 0;
if (idx == weights.length) {
return curVal;
}
if (dp[idx][curWeight] != -1) return dp[idx][curWeight];
int ans1 = 0;
int ans2 = 0;
if (curWeight + weights[idx] <= capacity) {
ans1 = helper(capacity, weights, values, dp, curWeight + weights[idx], curVal + values[idx], idx + 1);
ans2 = helper(capacity, weights, values, dp, curWeight, curVal, idx + 1);
dp[idx][curWeight] = Math.max(ans1, ans2);
}
ans2 = helper(capacity, weights, values, dp, curWeight, curVal, idx + 1);
dp[idx][curWeight] = ans2;
return dp[idx][curWeight];
}
public static int findMaxKnapsackProfit(int capacity, int[] weights, int[] values) {
int[][] dp = new int[weights.length + 1][capacity + 1];
for (int[] temp : dp)
Arrays.fill(temp, -1);
int ans = helper(capacity, weights, values, dp, 0, 0, 0);
return ans;
}
I am not able to figure out what am I doing wrong here or how to go about debugging this. I am memoizing using the same states as mentioned in other solutions but not sure why I am getting incorrect answer. Any help regarding this is higly appreciated.