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?


1 Answer 1


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$ Sep 7, 2010 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, 2016 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, 2021 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, 2021 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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