Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited number of objects of each type)? I'm writing an introduction to a few of these problems, and noticed that I hadn't really heard of a standard reduction here. Shouldn't be that hard (it's a relatively expressive problem), but I can't think of anything right now… Thoughts/references?


There is a simple reduction from the subset sum problem. (We usually give it as an exercise.)

The idea is to encode in the weights that an element can only be included 0 or 1 times.

Assume the subset sum instance consists of numbers $w_1,\dots,w_n$ with target $W$. Assume that $w_i < B$ for all $i$.

We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $i$ we get two new weights $w^1_i = (2^{n+1} + 2^i)nB + w_i$ and $w^0_i = (2^{n+1} + 2^i)nB$. The new weight bound is defined as $W' = (n2^{n+1} + 2^n + \dots + 2^1)nB + W$. Values of elements are the same as their weights, and the target value is $W'$

  • $\begingroup$ Right! Very nice. I pondered some sort of binary "powers-of-two" encoding to get from the unbounded to the bounded case, actually; just didn't think it through, I guess. Thanks a lot! $\endgroup$ – Magnus Lie Hetland Sep 7 '10 at 10:47
  • 1
    $\begingroup$ Could you please explain why we need the $n2^{n+1}$ term in each of the weights? $\endgroup$ – user44551 Jan 18 '16 at 21:10
  • $\begingroup$ @user44551 I suppose, this is to make sure we do not pick more than $n$ of the elements. Observe that (a) $W'$ is less than $(n + 1) 2^{n+1} nB$ and (b) taking more than $n$ elements is a sure way to get the weight of more than that. $\endgroup$ – kirelagin Jun 28 at 21:30
  • $\begingroup$ In fact, these terms guarantee that we take exactly $n$ elements, which, together with the bitmask thing, guarantees that we take exactly one element from each pair. $\endgroup$ – kirelagin Jun 28 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.