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 wi and profit pi, and two positive integers B and K, can we assign a non-negative integer ci to each item i such that:
- ci*wi ≤ B
- ci*pi ≥ 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* si , and 2*n. We’ll now create a set U for our Integer Knapsack instance with 2n elements:
Each element will be labeled uij, where i runs from 1 to n and j runs from 0 to 1. Element uij will have profit and weight n* Mn+1+ Mi + j*si
Our K’ (and B’) will be: n*Mn+1 + Mi + K.
If S has a subset that sums to K, then for each element i, if we took si in the solution, we take ui1 in our Integer Knapsack solution. Otherwise, we take ui0.
If U has an Integer Knapsack solution, we know that we have non-negative integer values cij such that cij*uij = K’. Because of the way we chose M, if we divide K’ by Mn+1 and round down, we get n. Because each uij has Mn+1 in it, dividing the summation side by Mn+1 gets us a number at least as big as the sum of the cij values. So we can say that yij is ≤ n. Thus, each element is taken at most n times.
Now we can go back to the original equation: cij*uij = K’ and do algebra. We learn that in fact, each cij is 0 or 1, and that ci0 + ci1 = 1 for all i (so we never take both ci0 and ci1), and that the values of ci1 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.