Integer Knapsack

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:

  • \sum_{i=1}^{n} ci*wi ≤ B
  • \sum_{i=1}^{n} 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:

  1. Profit 4, Weight 1
  2. Profit 6, Weight 2
  3. 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* \sum 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 + \sum_{i=1}^{n} 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 \sum_{i=1}^{n} \sum_{j=0}^{1} 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 \sum_{i=1}^{n}\sum_{j=0}^{1} yij is ≤ n.  Thus, each element is taken at most n times.

Now we can go back to the original equation: \sum_{i=1}^{n} \sum_{j=0}^{1} 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.

Leave a Reply

Your email address will not be published. Required fields are marked *