Knapsack Problems

Audience

This article is aimed at engineers with a reasonable understanding of algorithms but who are looking to learn about the knapsack problem.

The examples will be written in Java, so a superficial understanding will be useful, but even without it you should be able to muddle through.

We will also be using the notion of Dynamic Programming, which you can swot up on using my article here.

Argument

The knapsack problem is a combinatorics optimisation problem. Imagine we have a number of items, each with a weight, and a value. Our bag can only fit a certain total weight. Given these constraints our aim is to maximise the total value in the bag.

Note, there are different flavours of the problem.

  • 0–1: We can select each item once, and we cannot select a fraction of it (e.g. we take half an item).
  • Bounded: We can take each item multiple times, up to an upper limit.
  • Unbounded: We can take each item as many times as we like.
  • And many more…

This article will focus on the 0–1 version, which is the simplest and most common.

We lead by example.

We have an array of n items, which have values 20, 40, 50 and 60. The item’s weights are 7, 6, 7 and 3. The maximum weight (w) our bag can hold is 20.

We first draw up a matrix with w columns and n rows, where each cell represents the max value we can obtain with that row’s number of items, and that column’s total weight.

How we populate our matrix

We should be able to see there are some obvious base cases. For example, when the total weight we can carry is zero, we can’t carry anything! Our total value is zero.

Similarly, when there are no items to select from, we can’t have any value there either. We fill up the first row and column.

Populating the base cases

From here we begin populating our matrix. As we move down our rows we can either include a new available item or not.

Let’s take the example of being on column 15, and we’re moving down to row 3.

We can either include item three in our solution or not. If we do include item three then our capacity (15) will reduce by the weight of that item (8). Remember we can only select from items one and two.

We’ve already calculated the optimal configuration in the case where we have capacity 15 — 8 = 7 and can only select from items one and two, it’s in our matrix at row 2, column 7.

If we don’t include item three in our solution then our optimal value is the same as the one where we chose between items one and two with our maximum capacity as 15. Our only issue is comparing the two and populating the matrix.

How we populate our matrix

Our answer is then the value in our matrix at the last row and column.

With all of this ironed out, let’s code up a solution.

Conclusion

In conclusion we have gone through the knapsack problem, how we solve it, and some example code.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
James Collerton

James Collerton

Senior Software Engineer at Spotify, Ex-Principal Software Engineer at the BBC