Discrepancy in Recursive and Memoized Knapsack Solution

15 Views Asked by At

I'm currently working on a knapsack problem and have implemented both a recursive solution without memoization and a memoized version. Surprisingly, the recursive solution is giving me the correct answer, but when I try to memoize the solution, I'm getting an incorrect result.

Recursion Code which gives correct output .

class Solution 
{ 
    //Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int W, int wt[], int val[], int n) 
    {   
         // your code here 
        int[][] dp = new int[n + 1][W + 1];
        for(int[] arr : dp) {
            Arrays.fill(arr, -1);
        }
        return recursion(0, 0, W, wt, val, dp);
    } 
    
    private static int recursion(int ind, int curVal, int curWeight, int[] weights, int[] values, int[][] dp) {
    // Base cases
    if (curWeight < 0) {
        return (int) (-1e9);
    }
    if (ind == weights.length) {
        return curVal;
    }
    if (curWeight == 0) {
        return curVal;
    }



    // Calculate the maximum value considering two options: including the current item or not
    int pick = recursion(ind + 1, curVal + values[ind], curWeight - weights[ind], weights, values, dp);
    int nonPick = recursion(ind + 1, curVal, curWeight, weights, values, dp);

    return Math.max(pick, nonPick);

}

}

The Memorization Code:

private static int memoization(int ind, int curVal, int curWeight, int[] weights, int[] values, int[][] dp) {
    // Base cases
    if (curWeight < 0) {
        return (int) (-1e9);
    }
    if (ind == weights.length) {
        return curVal;
    }
    if (curWeight == 0) {
        return dp[ind][curWeight] = curVal;
    }

    // If the result is already calculated, return it
    if (dp[ind][curWeight] != -1) {
        return dp[ind][curWeight];
    }

    // Calculate the maximum value considering two options: including the current item or not
    int pick = memoization(ind + 1, curVal + values[ind], curWeight - weights[ind], weights, values, dp);
    int nonPick = memoization(ind + 1, curVal, curWeight, weights, values, dp);

    // Store the result in the memoization table
    dp[ind][curWeight] = Math.max(pick, nonPick);

    return dp[ind][curWeight];
}
0

There are 0 best solutions below