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 U_{1} through U_{m}, a maximum capacity C and a goal value K. Can we pick a *single* element u_{i} from each U_{i}, and assign each one a rational number r_{i} between 0 and 1 to each on so that the sum of all r_{i}*s(u_{i}) is ≤ B and the sum of all r_{i}*v(u_{i}) 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:

Item | Value | Size |

1 | 8 | 7 |

2 | 10 | 10 |

3 | 6 | 8 |

and partition 2 was:

Item | Value | Size | |

1 | 3 | 9 | |

2 | 2 | 2 | |

3 | 1 | 6 |

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 U_{i} set for each element in the initial Knapsack instance. Each will each have 2 elements: u_{i1} has value R+v(i) and size s(i). u_{i2} 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 u_{i1 }or u_{i2}. We then either add v(i) to our value (if we take u_{i1}) or 0 to it (if we take u_{i2}))

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 u_{i1} from each set corresponds to taking u_{i} 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.