Несоответствие в рекурсивном и мемоизированном решении о рюкзаке ⇐ JAVA

[Гость]

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]; }

Источник: https://stackoverflow.com/questions/781 ... k-solution