How to solve 0/1 knapsack problem using memoization DP by incrementally adding the capacity instead of substracting

69 Views Asked by At

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.

0

There are 0 best solutions below