The Knapsack Problem

Learn a Java implementation of the knapsack problem interview question.

Imagine that you’re a thief breaking into a house. There are so many valuables to steal - diamonds, gold, jewelry, and more! But remember, you’re just one person who can only carry so much. Each item has a weight and value, and your goal is to maximize the total value of items while remaining within the weight limit of your knapsack. This is called the knapsack problem and is commonly used in programming interviews. We will solve this problem in two ways: recursively, and using dynamic programming.

The Problem

The first step to solving this problem is to understand the parameters involved. You will be given:

• the total amount of weight you can carry (`weightCap`)
• the weights of all of the items in an array (`weights`)
• the values of all of the items in an array (`values`)

Your function should return the maximum value that you will be able to carry.

An Example

Let’s say that you have a knapsack that can only carry 5 pounds, and the house you’re robbing has three items that you want to steal:

1. A ring that weighs 1 pound with a value of \$250
2. Earrings that weigh 3 pounds with a value of \$300
3. A necklace that weighs 5 pounds with a value of \$500

This information can be summarized as follows:

``````weightCap = 5
weights = [1, 3, 5]
values = [250, 300, 500]``````

You have four possible ways to fill your knapsack:

1. Take only the ring, giving you \$250
2. Take only the earrings, giving you \$300
3. Take only the necklace, giving you \$500
4. Take the ring and the earrings, giving you \$550

Since the ring and the earrings have a combined weight of 4 pounds, taking both gives you the maximum value while staying within your weight capacity. Now that you’re familiar with the problem, let’s take a look at two different approaches to solving it!

The Recursive Solution

The brute force solution to this problem is to look at every subset of the items that has a total weight less than `weightCap`. Then you simply take the maximum of those subsets, giving you the optimized subset with the highest value possible.

You will need an additional parameter, `i`, that tells us where we are in the list of items. With each step, we will break the problem down into subproblems, and compare them to find the maximum value. There are three possibilities for every call of the function:

1. `weightCap` or `i` are zero, meaning the knapsack can hold no weight, or there are no more items to look at. In either case, we return `0`.
2. The weight of the item we’re looking at exceeds `weightCap`, in which case we just move on, calling the function on the next item.
3. If neither of the above are true, that means we have to consider whether or not the item we are at (`i`) should be included in the optimal solution.

Steps 1 and 2 from above can be solved as follows:

``````public class Knapsack {

static int knapSack (int weightCap, int weights[], int values[], int i)
{
if (i == 0 || weightCap == 0) {
return 0;
}

else if (weights[i - 1] > weightCap) {
return knapSack(weightCap, weights, values, i - 1);

}
}
}``````

For step 3, we need to look at both situations and determine if we want to include this item in our optimized solution or not.