educative.io

Error In 0/1 Knapsack DP code

Courses
, ,
#1

I need help un identifying error in my code. I tried below code for input
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};

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 = helper(capacity, weights, values, dp, curWeight + weights[idx], curVal + values[idx], idx + 1);
    int ans2 = helper(capacity, weights, values, dp, curWeight, curVal, idx + 1);
    dp[idx][curWeight] = Math.max(ans1, 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;
}

It’s giving me answer 2245 instead of 2255. I am not sure what am I doing wrong.

1 Like
#2

Hello @SHASHANK1,

I appreciate your message and have carefully reviewed the code you provided for the Knapsack Problem. After further analysis, I identified an issue in the indexing of the values and weights arrays during the recursive calls. I have made the necessary corrections to the code. Please find the updated and corrected version below:

public class Knapsack {
    public static int findMaxKnapsackProfit(int capacity, int[] weights, int[] values, int n) {
        int[][] dp = new int[n + 1][capacity + 1];

        for (int[] temp : dp)
            Arrays.fill(temp, -1);

        int ans = helper(capacity, weights, values, dp, 0, n);
        return ans;
    }

    public static int helper(int capacity, int[] weights, int[] values, int[][] dp, int idx, int n) {
        if (idx == n || capacity == 0)
            return 0;

        if (dp[idx][capacity] != -1)
            return dp[idx][capacity];

        if (weights[idx] <= capacity) {
            int ans1 = values[idx] + helper(capacity - weights[idx], weights, values, dp, idx + 1, n);
            int ans2 = helper(capacity, weights, values, dp, idx + 1, n);
            dp[idx][capacity] = Math.max(ans1, ans2);
            return dp[idx][capacity];
        }

        dp[idx][capacity] = helper(capacity, weights, values, dp, idx + 1, n);
        return dp[idx][capacity];
    }
}

  • The initial call to the helper method should not pass 0 as the initial value for curVal . Instead, the initial value is accumulated in the recursive calls.

  • The recursive call should use the current index idx to access the correct elements in the weights and values arrays. This ensures that the weight and value of the current item are considered in the recursive calculations.

  • The base case should check if we have reached the end of the items (idx == n ) or if the remaining capacity is zero (capacity == 0 ). This ensures that the recursion stops when we have considered all items or when the knapsack is full.

These adjustments collectively address the indexing issues and ensure that the recursive calls correctly consider the weights and values of the items. The corrected code should now provide the accurate output for the Knapsack Problem.

I hope this explanation helps in understanding the changes made in to your original code. Please feel free to share any more suggestions and feedbacks. We’d be happy to help. Thanks!

Happy learning!