The knapsack problem is a key one in computer science, and has received a lot of attention over the years. The goal is to best fill a bag of capacity *M*kg with items {*1..N*} that each have a weight and a value, so that the bag is as valuable as possible. For example, we want to fill a bag that has a capacity of 5kg using 4 items:

- onions weighing 3kg, value £2
- carrots weighing 1kg, value £3
- potatoes weighing 4kg, value £4
- tomatoes weighing 2kg, value £6

It’s obvious here that the best thing to do here is to take just the carrots and the tomatoes, even though there will still be some spare capacity.

The key idea to solve this problem is that the initial problem can be split into smaller overlapping subproblems. Suppose we have already decided that the optimal combination for a bag that weighs 4kg using just the first two items, carrots and onions, is to take both items. Then, we consider whether it’s possible to do better by allowing the third item, potatoes. That is, we either take out the carrots and onions and replace them with the potatoes, or we leave the bag as it is without the potatoes in.

Formally, we can solve the problem with dynamic programming by defining *wi* as the weight of item i and *vi* as it’s value. We index weight by j, and build an MxN table, where entries V(i,j) can be filled in by

V(i,j) = max V(i-1,j)
V(i-1,j-wi) + vi

The knapsack problem has many practical applications, and is particularly applicable to those that come under the umbrella of *resource allocation*. For example, assigning limited funds among a number of different research projects to get the best expected value for money.

### Like this:

Like Loading...

*Related*