The Knapsack Problem and Dynamic Programming

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 Mkg 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.

Advertisements
This entry was posted in Technology and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s