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.