AlgoDaily - Knapsack Problem

Home > Dynamic Programming > Dynamic Programming > Knapsack Problem

Memoization: Optimizing the Recursive Solution

In the previous screen, we implemented a recursive solution for the knapsack problem using the top-down approach. However, this solution can be inefficient as it recalculates solutions for overlapping subproblems.

To improve the performance of the recursive solution, we can apply the concept of memoization.

Memoization is a technique that involves caching the results of expensive function calls and reusing them when the same inputs occur again.

In the case of the knapsack problem, we can create a memoization table to store the results of subproblems that have already been solved.

Here's an updated implementation of the recursive knapsack solution with memoization in C#:

xxxxxxxxxx
}
 
public class Knapsack
{
    private int[,] memoizationTable;
    
    public int RecursiveKnapsack(int[] weights, int[] values, int capacity, int index)
    {
        if (index < 0 || capacity <= 0)
        {
            return 0;
        }
        
        if (memoizationTable[index, capacity] != -1)
        {
            return memoizationTable[index, capacity];
        }
        
        int include = 0;
        if (weights[index] <= capacity)
        {
            include = values[index] + RecursiveKnapsack(weights, values, capacity - weights[index], index - 1);
        }
        
        int exclude = RecursiveKnapsack(weights, values, capacity, index - 1);
        
        int result = Math.Max(include, exclude);
        memoizationTable[index, capacity] = result;
        
        return result;
    }

Memoization: Optimizing the Recursive Solution

Programming Categories

Popular Lessons