I recently flew on an airline that permitted me to carry a single personal item. No check-in luggage, no carry-on luggage. Personal items had to fit in a 17" L x 13" W x 8" H space, so I used a school backpack. As I stuffed my bag with clothing and toiletry and electronics, I became acutely aware of my situation's resemblance to the knapsack problem, an NP-complete optimization problem introduced to me during my college days.

The problem

Given a set of n items, where each item x has a weight wx and a value vx, determine the optimal number of each item to put in a knapsack such that the total weight is at or below a fixed W and the total value is maximized.

At first glance, this problem may not seem difficult, but it's believed that no polynomial-time algorithm can correctly solve it. In fact, not only is the original optimization problem difficult, but we don't even believe that its sibling decision problem can be solved in polynomial time either: Can a total value V be obtained without exceeding W?

A solution

There exist various approximation and meet-in-the-middle algorithms to solve the knapsack problem, but my favorite solution is the classic dynamic programming one. In this solution, a matrix is built with n+1 rows and W+1 columns. Row i in the matrix corresponds to a knapsack filled with only items 1 through i. Column j corresponds to a knapsack with weight capacity j. (Both i and j are zero-indexed, but items are numbered starting from one.) Then, each entry in the matrix is filled in with the largest value that can be obtained for that row and column.

For example, the entry in the third row and seventh column will store the maximum value that can be achieved using only items 1, 2, 3 in a knapsack that can support a maximum weight of 7. Set up in this way, our matrix consists of several subproblems that can be filled in from the top-left corner to the bottom-right one, helping us to solve our knapsack problem. The entry in the last row and rightmost column corresponds to the maximum total value when all items are used to fill a knapsack with weight capacity W. That's our solution!

To fill in the matrix, we first start with the base cases. The first row uses 0 items, so the maximum value that can be obtained for any of those entries is 0. The first column has weight capacity 0, so the maximum value that can be obtained for any of those entries is also 0. Easy enough.

Then, we work through each row from top to bottom, left to right. When looking at the next row, we have one new item to work with, and we have the choice of whether or not to add it to the knapsack. If there's room, we definitely add the item, because it increases the total value without going over the maximum weight. In this case, the entry's value is the sum of the new item's value and the maximum value calculated for that weight before the current item was considered, i.e. the entry in the previous row and same column.

However, if there's not enough room, we calculate two alternative values and choose the larger of them: 1) the value when we remove previous items from the knapsack until the new item can be added or 2) the value when we don't add the new item at all. Both of these are calculated by examining various entries in the above row.

And that's it. We fill in the entire matrix until our solution entry is filled in, and then we're done. This dynamic programming solution requires us to assess roughly n rows and W columns, so it isn't polynomical, but it is correct.

As for flying with a single bag, I ended up leaving out my towel and second jacket so that I could fit in my running shoes and climbing shoes. I think the trade-off was worth it. I can always buy a towel or jacket at my final destination if I need it!