MP9 is Knapsack

The next problem seems like an easy variant of Knapsack, and I tried for a while to find a quick easy reduction. When I finally caved and looked up the reference, I found that it wasn’t easy at all. Which made me feel good, at least, that I wasn’t missing something, but I do still feel like there should be an easier way to do this.

**The problem: **Integer Knapsack. This is problem MP10 in the appendix.

**The description: **Given a set of elements, each item i has weight w_{i} and profit p_{i}, and two positive integers B and K, can we assign a non-negative integer c_{i} to each item i such that:

- c
_{i}*w_{i}≤ B - c
_{i}*p_{i}≥ K?

**Example: **This is just the classic Knapsack problem where we are allowed to take more than one of each item. So, suppose we have 3 items:

- Profit 4, Weight 1
- Profit 6, Weight 2
- Profit 3, Weight 3

No matter what our B is, in the original 0/1 problem, we could only possibly get a profit of 13. But here, if we say that B is 10, we could get a profit of 40 by taking the first item 10 times.

**Reduction: **It really seems very close to regular Knapsack, doesn’t it? G&J even say that the reduction is from Sum of Subsets, just like our Knapsack reduction did. But the reference from Lueker is actually pretty complicated:

We’re given a Sum of Subsets instance- a set S with n elements and a value K to try to hit exactly.

Define M to be 1+ the max of K, n* s_{i} , and 2*n. We’ll now create a set U for our Integer Knapsack instance with 2n elements:

Each element will be labeled u_{ij}, where i runs from 1 to n and j runs from 0 to 1. Element u_{ij} will have profit and weight n* M^{n+1}+ M^{i} + j*s_{i}

Our K’ (and B’) will be: n*M^{n+1} + M^{i} + K.

If S has a subset that sums to K, then for each element i, if we took s_{i} in the solution, we take u_{i1} in our Integer Knapsack solution. Otherwise, we take u_{i0}.

If U has an Integer Knapsack solution, we know that we have non-negative integer values c_{ij} such that c_{ij}*u_{ij} = K’. Because of the way we chose M, if we divide K’ by M^{n+1} and round down, we get n. Because each u_{ij} has M^{n+1} in it, dividing the summation side by M^{n+1} gets us a number at least as big as the sum of the c_{ij} values. So we can say that y_{ij} is ≤ n. Thus, each element is taken at most n times.

Now we can go back to the original equation: c_{ij}*u_{ij} = K’ and do algebra. We learn that in fact, each c_{ij} is 0 or 1, and that c_{i0} + c_{i1} = 1 for all i (so we never take both c_{i0} and c_{i1}), and that the values of c_{i1} are 0/1 solutions to the corresponding elements in the Sum of Subsets problem.

**Difficulty: **7. There seems to be no natural reason to for this definition of M except “that’s what made it work”. I wish there was an easier reduction.