It’s kind of amazing that I’ve gotten this far without needing such a classic problem. But I was writing up the next post and needed to link to my Knapsack article, and it wasn’t there, so..
The problem: Knapsack. (More technically, “0/1 Knapsack”). This is problem MP9 in the appendix.
The description: Given a set U of items, each item u in U has a profit p(u), and a weight w(u). (G&J call these “value” and “size”), and positive integers B and K. Can we create a subset U’ of U that has total profit at least K, but total weight at most B?
Example: Knapsack is one of my all-time favorite problems, which probably says something about me. But I inflict it on my students at all levels of the curriculum – it’s a good motivation to introduce parallel arrays, and building simple classes at the low levels, the fractional version is a good example of a greedy algorithm, and the 0/1 version is a good example of where greedy fails. It also fascinates me how it’s an example of a problem where a problem that has infinite solutions (Fractional Knapsack, when you can take any proportion of an item) is easily solvable, but a problem that has fewer solutions to consider (0/1 Knapsack, where there are “just” 2 choices for each item) is intractable.
Anyway, here is my classic “Your Greedy Approach Won’t Work” example:
If B=6, the best option is to choose items 2 and 3. But greedily picking items by profit/weight ratio (which works for the Fractional Knapsack problem) will choose item 1, and lose profit.
Reduction: G&J reference Karp’s paper and this is a classic reduction you see in most books that do this problem. You go from Subset Sum. We’re given a set S, and an integer K. We create a set U with the same number of elements, make the profit and weight of each element the same, and equal to the size of the corresponding element in S. We set K’=B=K.
If the original set had a subset summing to K, then taking those elements will make us a profit of K’ and a weight of B.
If we have a Knapsack solution with profit K’ or more, then since the profits of all items are equal to their weights, the only for the total weight to not exceed B is for the profit to be exactly K’. So taking the corresponding items in S will get a sum equal to exactly K.
Difficulty: 3. I use this as an easy homework or test question all the time.