We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Knapsack
  5. Discussions

Knapsack

  • icristianhrimiuc
     + 0 comments

    As people have already stated, there are errors in the way the problem was formulated, but it is still solvable. This was my inneficient but workable C# solution:

    private static int[] memo;

public static int unboundedKnapsack(int sum, List<int> arr, bool resetMemo = true)
{
    if (resetMemo) memo = new int[sum + 1];

    if (sum == 0 || arr.Count == 0) return 0;

    if (memo[sum] > 0) return memo[sum];

    var maxSum = 0;
    for (var i = 0; i < arr.Count; i++)
    {
        if (arr[i] <= sum)
        {
            maxSum = Math.Max(maxSum, arr[i] + unboundedKnapsack(sum - arr[i], arr, false));
        }
    }

    memo[sum] = Math.Max(maxSum, memo[sum]);
    return maxSum;
}