This week we have a variant of the Knapsack problem that feels like greedy methods shold work on. G&J actually provide several variants of this problem that the greedy approach would give us a polynomial solution.
The problem: Continuous Multiple Choice Knapsack. This is problem MP11 in the appendix.
The description: Given a set of elements U, each element u in U has a positive size (s(u)) and value (v(u)). We’re also given a partition of U into m disjoint sets U1 through Um, a maximum capacity C and a goal value K. Can we pick a single element ui from each Ui, and assign each one a rational number ri between 0 and 1 to each on so that the sum of all ri*s(ui) is ≤ B and the sum of all ri*v(ui) is ≥ K?
Example: This seems like a problem where a solution similar to the greedy solution to fractional Knapsack should work- take the highest vaalue per size that you can. This fails because you can only take 1 of each item, and you may need to take a less profitable item (in terms of ratio) with a higher total value.
For example, if partition 1 was:
and partition 2 was:
If K was 10, we could get 10 profit using only 9 size by taking all of item 1 from partition1 and all of item 2 from parttion 2. But is 12, we can only do that by taking item 2 from parittion 1, which gives us a total size of 12.
Reduction: G&J say to use Partition, but the paper by Ibaraki that I have uses 0/1 Knapsack. Define R to be a number > the max of all of the values * (the max of all of the weights -1). We will construct a Ui set for each element in the initial Knapsack instance. Each will each have 2 elements: ui1 has value R+v(i) and size s(i). ui2 has value R and weight 0. We’ll keep the same B. Our K’ will be n*R+K. (He doesn’t explicitly say this, instead proving that the optimial solution for this problem exists if and only if the corresponding items are taken for the 0/1 Knapsack problem. But each element contributes at least R to the total value, whether we take ui1 or ui2. We then either add v(i) to our value (if we take ui1) or 0 to it (if we take ui2))
Ibaraki shows that optimal solutions to this problem only ever take at most one fractional item- they take 0 or 1 of every other item. He then shows that in this specific instance, you won’t take any fractional items.
He then proves that taking the ui1 from each set corresponds to taking ui once in the original Knapsack. Which is pretty straightforward.
Difficulty: 6. This is actually not that hard of a reduction, except for the need to pick a “big enough” R. I’m not entirely sure why the chosen R is big enough, but other values aren’t. The rating also assumes that you tell the students about the “maximum one fractional value” fact.