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

Sort by

recency

|

266 Discussions

|

  • david_mtz_enciso
     + 0 comments

    there is an error in the solution class, is just running one test

  • david_mtz_enciso
     + 0 comments

    there is an error in the solution class, is just running one test

  • heliomolive
     + 0 comments

    For JavaScript is also needed to fix the main.

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

  • LeftNutz
     + 1 comment

    Annoyingly ... we hade to update the main function to get the code to loop through all test cases ... shoulda put that in the instructions.