Knapsack performance issue

Question

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

Answer 1

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 "numberOfItemsToConsider" 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() + "_" + 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.

Answer 2

// 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 Run(int n, int maxWeight, int[] weights, int[] values)
{

In general: IMO it's bad design if you use static members as state members. Here it's maybe unimportant because it's just an exercise, but in real world you shouldn't do that, because it's asking for trouble if you for instance run the code in two different threads at the same time.

So change them to instance members and provide a static starter method like:

public class Knapsack
{
  private int n;
  private int maxWeight;
  private int[] weights;
  private int[] values;

  public Knapsack(int n, int maxWeight, int[] weights, int[] values)
  {
    this.n = n;
    this.maxWeight = maxWeight;
    this.weights = weights;
    this.values = values;
  }

  public long Run()
  {
    // TODO: The algorithm
  }

  public static long Solve(int n, int maxWeight, int[] weights, int[] values)
  {
    Knapsack solution = new Knapsack(n, maxWeight, weights, values);
    return solution.Run();
  }
}

---

Besides that, I won't mention that you should separate the input handling and the processing into different classes.

---

When it comes to the algorithm it self, I have tried to clean it up a bit:

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;

  long result = Solve(weightLeft, numberOfItemsToConsider - 1);

  // 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, result);
    // Add the result to the memo dictionary.
  }

  s_memo[(weightLeft, numberOfItemsToConsider)] = result;
  return result;
}

It doesn't do much performance wise but, is maybe a little easier to follow.

---

A significant performance gain you'll only get, if you substitute the s_memo-dictionary with a two dimensional jagged array:

static long[][] valueTable = null;

public static void Run(...) {
  valueTable = Enumerable.Range(0, n + 1).Select(i => Enumerable.Range(0, maxWeight + 1).Select(_ => -1L).ToArray()).ToArray();