Knapsack performance issue 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&lt;(int, int), long&gt; 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&lt;(int, int), long&gt;(10000000);

    // Read each line from the input.
    for (int i = 0; i &lt; 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 &gt;= 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;
  }                          
}
```
Instead of storing the actual values in a tuple as the key in a dictionary for memoisation, multiplex them together into a single value and use that as the key. You will need to pick multiplex value that is an order of magnitude higher than the largest &quot;numberOfItemsToConsider&quot; you can expect. Or you could turn them into strings and concat for the key.
i.e.
var key = (weightLeft * 10_000) + numberOfItemsToConsider; // parens for readability.
// OR
var key = weightLeft.ToString() + &quot;_&quot; + numberOfItemsToConsider.ToString(); // parens for readability.

EDIT: Thanks @Jeff E for correcting me on this, Hashtable is slower.
Instead of a dictionary, you could use a hashtable, which is faster. i.e.
Finally, if you're chasing every little bit of time, allocate all your variables outside of any loops, so they are not continually being reallocated, which has an expense.