Solving (and Refactoring!) the Knapsack Problem in Java

This is part of a series where I take Exercism exercises and break down the process of coding and refactoring my solutions.

Intro: Understanding the Problem

The Knapsack Problem is often used as an introductory problem for dynamic programming. The basic premise is that you’ve received a bunch of items, each with a non-negative value and weight. For the sake of simplicity, we’ll assume both values are also integers. The question the Knapsack Problem poses is this: if we’re given a backpack with a carrying capacity of n, what combination of items with total weight less than n will give you the maximum value?

The algorithm for solving this problem involves some setup. Let’s define our Item class like so:

From there, we can define the basic ingredients for the algorithm. Let w be our carrying capacity and n be the number of items. If we brute-forced our way through this, we’d have a speed of about O(n * 2^n), which is really slow as the number of items increases. With dynamic programming, we can get that down to O(nw). To do that, we’ll need a 2D array of integers, with n + 1 rows and w + 1 columns, with all indexes set to -1.

Implementation

Here’s the main setup:

Here’s a question you should be asking:
Why are you storing the integer array and the items like that?

Exercism exercises come with built-in tests. The test setup for this one initializes with an empty constructor, and calls the maximumValue function
in the test. This forces me to either pass both the integer array and the list into the maxValueInRange as arguments or to put them in a scope where maxValueInRange could access them. In this case, because I want to limit my function arguments, I chose the latter.

Finally, we implement the function like so:

It passes all the tests! If you’re familiar with the problem, you might even be able to get what each part is doing! But it can be easy to feel lost looking at this. So let’s make this a little more readable.

Refactoring

What’s our goal here? When your aim is readability, my first instinct is always to make the code read more like English. It’s not doing that right now.

Let’s start with the argument names.

private int maxValueInRange(int i, int j)

i and j can be confusing as axis labels, since math folks typically use the first axis to describe horizontal movement instead of vertical movement. Let’s make our labeling unambiguous by naming them row and column, respectively. While we’re at it, let’s rename the array, since it makes more sense to describe it as a table of maximum values.

private int[][] maxValues;
private int maxValueInRange(int row, int column) {}

Next, the first conditional.

if (i == 0 || j <= 0) {
    return 0;
}

This part of the algorithm checks if we’re in a row or column that’s out of bounds. It’s small, but putting this boolean into its own function lets us redefine the bounds checking separately from the rest of the function if we ever need to do that.

private static boolean isOutOfBounds(int row, int column) {
    return row == 0 || column <= 0;
}

Results in:

if (isOutOfBounds(row, column)) {
    return 0;
}

At each step, make sure you’re checking that all the tests still pass. It’s important to do this process in small steps.
Next, let’s look at the way we access the weights and values.

items.get(row - 1).weight

This is a really long identifier to put inside an array accessor, especially when compounded with additional operations. Let’s move these to their own functions as well. Since the items are 0-indexed, and the Wikipedia implementation assumed the list was 1-indexed, we had to specify that offset every time we called the method, which was begging for a bug. This gets rid of that issue as well.

private int weightAt(int index) {
    return items.get(index - 1).weight;
}

private int valueAt(int index) {
    return items.get(index - 1).value;
}

Next, let’s clean up our repetition. Notice how we only over offset the row by -1, and only offset the column by the weight associated with the row index? Let’s assign these to variables at the first places they’re needed. We need to calculate the previous row before the method’s second if statement, and we need to calculate the previous column at the start of the else statement. We assign both as follows:

int previousRow = row - 1;
int previousColumn = column - weightAt(row);

Now we only need to calculate that value once, instead of every time we need it. After we’ve replaced all the array accesses with these, you’ll notice things getting a bit more compact.

Lastly, we make the check for calculating a new value at an index if it’s empty into its own method, shouldCalculate:

private boolean shouldCalculate(int row, int column) {
    return valueTable[row][column] == -1;
}

The conditional for checking if the item weight is too large for the carrying capacity at the given column reads intuitively, so I decided not to refactor it into anything more prose-like, since the operator does that work for me.

Conclusion

We’re done! The finished code looks like this:

You can see this solution and about 25 others over at my GitHub.

Thanks for reading!