# Simple reduction to unbounded knapsack?

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?

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'$
• Could you please explain why we need the $n2^{n+1}$ term in each of the weights? Jan 18 '16 at 21:10
• @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. Jun 28 at 21:30
• 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. Jun 28 at 22:50