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