Algorithms for Coding Interviews in Java/

...

/

Solution: The 0/1 Knapsack Problem

Solution: The 0/1 Knapsack Problem

This review provides a detailed analysis of the different ways to solve The Knapsack Problem.

We'll cover the following...

Solution #1: Brute force

Press + to interact
class KnapsackProblem
{ 
  // Returns the maximum value that can be put in a knapsack of capacity W 
  public static int knapSack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity, int currentIndex) {
    // Base Case 
    if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0 || weightsLength != profitsLength)
      return 0;
    // If weight of the nth item is more than Knapsack capacity W, then 
    // this item cannot be included in the optimal solution
    int profit1 = 0;
    if (weights[currentIndex] <= capacity)
      profit1 = profits[currentIndex] + knapSack(profits, profitsLength, weights, weightsLength, capacity - weights[currentIndex], currentIndex + 1);
    int profit2 = knapSack(profits, profitsLength, weights, weightsLength,  capacity, currentIndex + 1);
    // Return the maximum of two cases:  
    return Math.max(profit1, profit2);
  }
  // Driver program to test above function 
  public 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
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4,  7, 0));
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4, 6, 0));
  }
};

Explanation

We start from the beginning of the weight array and check if the item is within the maximum capacity as done on line 12. If it is within the maximum capacity, we call the knapsack() function recursively with the item and save the result in profit1 (line 13).

Then, we call the function recursively excluding the item and saving the result in the variable profit2 (line 15).

Out of the two, we return the result that has higher profit (as done on line 18).

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 arrays remain constant, and only the capacity and the current index change. For simplicity, let’s denote capacity with C and current index with n:

%0 node_1 ... node_1727700216276 n:3, C:2 node_1->node_1727700216276 node_1727700350599 n:2, C:2 node_1727700216276->node_1727700350599 node_1727700351539 n:1, C:1 node_1727700216276->node_1727700351539 node_1727700390214 n:1, C:2 node_1727700350599->node_1727700390214 node_1727700432997 n:1, C:1 node_1727700350599->node_1727700432997 node_1727700493058 n:0, C:2 node_1727700390214->node_1727700493058 node_1727700520953 n:0, C:1 node_1727700390214->node_1727700520953 node_1727700535287 n:0, C:1 node_1727700432997->node_1727700535287 node_1727703936761 n:0, C:0 node_1727700432997->node_1727703936761 node_1727700386005 n:1, C:1 node_1727700351539->node_1727700386005 node_1727704285383 n:1, C:0 node_1727700351539->node_1727704285383 node_1727704015765 n:0, C:1 node_1727700386005->node_1727704015765 node_1727703992590 n:0, C:0 node_1727700386005->node_1727703992590
A recursive tree with overlapping sub-problems at certain levels.

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 have that many calls. The logic is similar to the one presented in the time complexity calculation of Fibonacci numbers. This is mostly owing to the overlapping subproblems. Let’s see how you can reduce it with a dynamic programming approach.

Solution #2: Top-down dynamic programming approach with memoization

Press + to interact
class KnapsackProblem
{ 
  public static int knapsackRecursive(int [][] lookupTable, int profits[], int profitsLength, int weights[], int weightsLength, int capacity, int currentIndex) {
    // base checks  
    if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0 || weightsLength != profitsLength)
      return 0;
    // if we have already solved the problem, return the result from the table  
    if (lookupTable[currentIndex][capacity] != 0)
      return lookupTable[currentIndex][capacity];
    // recursive call after choosing the element at the currentIndex
    // if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
    int profit1 = 0;
    if (weights[currentIndex] <= capacity)
      profit1 = profits[currentIndex] + knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength,
        capacity - weights[currentIndex], currentIndex + 1);
    // recursive call after excluding the element at the currentIndex
    int profit2 = knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, currentIndex + 1);
    lookupTable[currentIndex][capacity] = Math.max(profit1, profit2);
    return lookupTable[currentIndex][capacity];
  }
  public static int knapSack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity) 
  {
    int lookupTable[][] = new int [profitsLength][];
    for (int i = 0; i < profitsLength; i++) {
      lookupTable[i] = new int[capacity + 1];
      for (int j = 0; j < capacity + 1; j++)
        lookupTable[i][j] = 0;
    }
    return knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, 0);
  }
  public 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
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4,  7));
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4, 6));
  }
};

Explanation

The function knapSack makes a lookupTable within the function that stores the maximum value that can be attained with maximum capacity (lines 29-35). This function calls ...