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

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

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

<p>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'$</p>

CC BY-SA 3.0
2016-01-18T21:10:02.450Z
Could you please explain why we need the $n2^{n+1}$ term in each of the weights?
user44551
CC BY-SA 4.0
2021-06-28T21:30:42.077Z
@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.
kirelagin
CC BY-SA 4.0
2021-06-28T22:50:24.590Z
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.
kirelagin
CC BY-SA 2.5
2010-09-07T10:47:27.520Z
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!
Magnus Lie Hetland
CC BY-SA 2.5
2010-09-05T19:33:12.820Z
2010-09-05T19:33:12.820Z
Kristoffer Arnsfelt Hansen
<p>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?</p>

CC BY-SA 2.5
2010-09-05T14:41:00.940Z
It seems that for a constant number of variables (object types), the UBK problem can be solved in polynomial time: http://books.google.com/books?id=u5DB7gck08YC&pg=PA211
Magnus Lie Hetland
CC BY-SA 2.5
2010-09-05T17:19:33.567Z
Wikipedia gives this reference for NP-hardness: http://en.wikipedia.org/wiki/List_of_knapsack_problems#cite_note-0
Jukka Suomela
<cc.complexity-theory><ds.algorithms><np-hardness><reductions>
Simple reduction to unbounded knapsack?
Magnus Lie Hetland
# Simple reduction to unbounded knapsack?

(Asked by: username_0 on 2010-09-05)

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?

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, reductions
> **Comments:**
> **username_0**: It seems that for a constant number of variables (object types), the UBK problem can be solved in polynomial time: http://books.google.com/books?id=u5DB7gck08YC&pg=PA211  
> **username_1**: Wikipedia gives this reference for NP-hardness: http://en.wikipedia.org/wiki/List_of_knapsack_problems#cite_note-0  

---

## 1 answers

### Answer by username_2 on 2010-09-05. Score: 7 | Accepted answer

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'$

> **Comments:**
> **username_0**: 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!  
> **username_3**: Could you please explain why we need the $n2^{n+1}$ term in each of the weights?  
> **username_4**: @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.  
> **username_4**: 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.  

---

