Solution: The 0/1 Knapsack Problem

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

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) ...

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.