Algorithms for Coding Interviews in C++/

...

/

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
#include <iostream>
using namespace std;
// Returns the maximum value that can be put in a knapsack of capacity W 
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 capacity W, 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 max(profit1, profit2);
}
int knapSack(int profits[], int profitsLength, int weights[], int capacity) {
  return knapsackRecursive(profits, profitsLength, weights, capacity, 0);
}
int main() {
  int profits[] = {1, 6, 10, 16}; // The values of the jewelry
  int weights[] = {1, 2, 3, 5}; // The weight of each
  cout << "Total knapsack profit = " << knapSack(profits, 4, weights, 7) << endl;
  cout << "Total knapsack profit = " << knapSack(profits, 4, weights, 6) << endl;
}

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

Then we call the function recursively excluding the item, and saving the result in the variable, profit2. Out of the two, we return the result that is greater (as done on line 21).

Pseudocode

for each item 'i' starting from the end
  create a new set which INCLUDES item 'i' if the total weight does not exceed the capacity, and recursively process the remaining capacity and items
  create a new set WITHOUT item 'i', and recursively process the remaining items 

return the set from the above two sets with higher profit

Let’s draw the recursive calls to see if there are any overlapping sub-problems. 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 n:3, C:2 node_2 n:2, C:2 node_1->node_2 node_3 n:2, C:1 node_1->node_3 node_1551887656977 n:1, C:2 node_2->node_1551887656977 node_1551887616573 n:1, C:1 node_2->node_1551887616573 node_1551887781509 n:0, C:2 node_1551887656977->node_1551887781509 node_1551887720316 n:0, C:1 node_1551887656977->node_1551887720316 node_1551887752749 n:0, C:1 node_1551887616573->node_1551887752749 node_1551887848020 n:0, C:0 node_1551887616573->node_1551887848020 node_1551887694427 n:1, C:1 node_3->node_1551887694427 node_1551887734242 n:1, C:0 node_3->node_1551887734242 node_1551887787351 n:0, C:1 node_1551887694427->node_1551887787351 node_1551887826088 n:0, C:0 node_1551887694427->node_1551887826088

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. The logic is similar to the one presented in the ... ...

Access this course and 1400+ top-rated courses and projects.