🎶 I love to go a-wandering, a knapsack on my back 🎶
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.
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
60. The item’s weights are
3. The maximum weight (
w) our bag can hold is
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.
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.
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
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
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.
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.
In conclusion we have gone through the knapsack problem, how we solve it, and some example code.