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