0/1 Knapsack algorithm with memoization slow (C#) [closed]

I’m solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case.


Problem statement

There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of wi and a value of vi

Taro has decided to choose some of the N items and carry them home in a knapsack. The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W

Find the maximum possible sum of the values of items that Taro takes home.


The input is in the following form:

N W w1 v1 w2 v2 : wN vN 

N: Number of items.

W: Max weight I can have.

wi: ith weight.

vi: ith value.

Here is my solution to it:

using System; using System.Collections.Generic;  public static class Solution {   // Both s_weights and s_values will have the same length.   private static int[] s_weights; // array holding the weights of the items.   private static int[] s_values; // array holding the values of the items.   private static Dictionary<(int, int), long> s_memo; // memoization dictionary.    // NOTE: I cannot use an array instead of a dictionary here, cause it   // will be a very large 2d array and will give OutOfMemoryException.    public static void Main()   {     // Read the first line, which contains number of items and max weight.     string[] nw = Console.ReadLine().Split(' ');     // Parse n.     int n = int.Parse(nw[0]);     // Parse the max weight.     int maxWeight = int.Parse(nw[1]);      s_weights = new int[n];     s_values = new int[n];     // arbitrary high capacity dictionary to avoid resizing which is O(n).     s_memo = new Dictionary<(int, int), long>(10000000);      // Read each line from the input.     for (int i = 0; i < n; i++)     {       string[] wv = Console.ReadLine().Split(' ');       s_weights[i] = int.Parse(wv[0]);       s_values[i] = int.Parse(wv[1]);     }     // Start the recursion with the maximum weight and all the items.     Console.WriteLine(Solve(maxWeight, n));   }    private static long Solve(int weightLeft, int numberOfItemsToConsider)   {     // simple base case.     if (weightLeft == 0 || numberOfItemsToConsider == 0) return 0;      // If already calculated, get it from the dictionary.     if (s_memo.TryGetValue((weightLeft, numberOfItemsToConsider), out var cachedValue))     {       return cachedValue;     }      // Recursive call calculating the solution if we don't take the current item.     long dontTakeCurrent = Solve(weightLeft, numberOfItemsToConsider - 1);     long result;      // Can we take the current item? If yes, calculate the solution.     if (weightLeft >= s_weights[numberOfItemsToConsider - 1])     {       long takeCurrent = s_values[numberOfItemsToConsider - 1] + Solve(weightLeft - s_weights[numberOfItemsToConsider - 1], numberOfItemsToConsider - 1);       // Maximize the value between the two cases, taking or not taking the item.       result = Math.Max(takeCurrent, dontTakeCurrent);       // Add the result to the memo dictionary.       s_memo.Add((weightLeft, numberOfItemsToConsider), result);       return result;     }     // Here, we don't have another choice other than not taking the item.     result = dontTakeCurrent;     s_memo.Add((weightLeft, numberOfItemsToConsider), result);     return result;   }                           } 

Note: I’ve already asked the question in codereview but no answer until now, so I thought cs could be a better place to ask about it.