Algorithms for Coding Interviews in C#/

...

/

Solution: The 0/1 Knapsack Problem

Solution: The 0/1 Knapsack Problem

Explore various approaches to solving the 0/1 Knapsack problem in detail.

We'll cover the following...

Solution 1: Brute force

using System;
class Program
{
    /// <summary>
    /// Finds the maximum value that can be put in a knapsack.
    /// </summary>
    /// <param name="profits">The profit that can be gained by each item.</param>
    /// <param name="profitsLength">The number of pieces of jewelry.</param>
    /// <param name="weights">The weight of each piece of jewelry.</param>
    /// <param name="capacity">The maximum weight that the knapsack can hold.</param>
    /// <param name="currentIndex">Current index of the weights.</param>
    /// <returns>Maximum value that can be put in a knapsack.</returns>
    public static int KnapSackRecursive(int[] profits, int profitsLength, int[] weights, int capacity, int currentIndex)
    {
        // Base Case
        if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0)
        {
            return 0;
        }
        // If weight of the nth item is more than Knapsack, then
        // this item cannot be included in the optimal solution
        int profit1 = 0;
        if (weights[currentIndex] <= capacity)
        {
            profit1 = profits[currentIndex] + KnapSackRecursive(profits, profitsLength, weights,
                                                     capacity - weights[currentIndex], currentIndex + 1);
        }
        int profit2 = KnapSackRecursive(profits, profitsLength, weights, capacity, currentIndex + 1);
        // Return the maximum of two cases:
        // (1) nth item included
        // (2) not included
        return Math.Max(profit1, profit2);
    }
    /// <summary>
    /// Finds the maximum value that can be put in a knapsack.
    /// </summary>
    /// <param name="profits">The profit that can be gained by each piece of jewelry.</param>
    /// <param name="profitsLength">The number of pieces of jewelry.</param>
    /// <param name="weights">The weight of each piece of jewelry.</param>
    /// <param name="capacity">The maximum weight that the knapsack can hold.</param>
    /// <returns>Maximum value that can be put in a knapsack.</returns>
    public static int KnapSack(int[] profits, int profitsLength, int[] weights, int capacity)
    {
        return KnapSackRecursive(profits, profitsLength, weights, capacity, 0);
    }
    // Driver code to test the above function
    static void Main(string[] args)
    {
        int[] profits = { 1, 6, 10, 16 }; // The values of the jewelry
        int[] weights = { 1, 2, 3, 5 };   // The weight of each
        Console.WriteLine("Total knapsack profit = " + KnapSack(profits, 4, weights, 7));
        Console.WriteLine("Total knapsack profit = " + KnapSack(profits, 4, weights, 6));
    }
}

Explanation

We start at the beginning of the weight list and check if the item is within the maximum capacity on line 27.

For each item ii starting from the end:

  • We create a new set that includes item ii if the total weight does not exceed the capacity and recursively process the remaining capacity and items. We save the result in profit1 (line 27).
  • We create a new set without item ii, recursively process the remaining items, and save the result in the variable, profit2 (line 31).
  • We return the set from the above two sets with higher profit (line 36).

Let’s draw the recursive calls to see if there are any overlapping subproblems. As we can see, in each recursive call, the profits and weights lists remain constant, and only the capacity and the current index change. For simplicity, let’s denote capacity with j and the current index with n:

Press + to interact

Time complexity

The time complexity of the algorithm above is O(2n)O(2^n), i.e., exponential, where nn is the total number of items. This is because we will have that many calls. This is owing to the overlapping subproblems. Let’s see how we can reduce it with a dynamic programming approach.

Solution 2: Top-down

...