<p>I'd like to have an explicit reduction among these two problems:</p>

<p>(1) Unbounded Knapsack: Given a set of $n$ item <em>types</em> with weight $w_i$ and quality $q_i$ solve:</p>

<p>$$maximize \sum_{i=1}^n q_ix_i $$ with:
$$ \sum_{i=1}^n w_ix_i &lt; W\\
x_i &gt;= 0\ \in N
$$
i.e. fill up the knapsack as much as possible (up to W) with items, the items are not limited in numbers, you have an unbounded number of copies of item1 with weight $w_1$, and quality $q_1$, etc. So the variable $x_i$ are integers that denote how many copies of item $i$ are in a solution.</p>

<p>(2) The k-exact version of the above add another constraint:</p>

<p>$$ \sum_{i=1}^n x_i = k $$ </p>

<p>i.e. you must take exactly $k$ item in total. </p>

<p>I do not need an algorithm for the problems, but I'd like to have an explicit reduction from (1) to (2). For a fixed istance of (1) the maximum number of items in a solution is limited from above by $kmax = W / \min w_i$. Then I can solve (2) for all value of $k$ from $1$ to $kmax$ and take the maximum of the solutions, but I'd like to see if there is a better way or not.</p>

CC BY-SA 3.0
2017-02-23T17:23:46.400Z
Can you please make your question self-contained by defining the problems you are talking about precisely.
Jan Johannsen
CC BY-SA 3.0
2017-02-23T19:47:52.503Z
Done. I also added more details on what I need. Thanks.
Antonio Caruso
<np-hardness><reductions>
Reduction Unbounded Knapsack < k-Exact Unbounded Knapsack
Antonio Caruso
# Reduction Unbounded Knapsack < k-Exact Unbounded Knapsack

(Asked by: username_0 on 2017-02-23)

I'd like to have an explicit reduction among these two problems:

(1) Unbounded Knapsack: Given a set of $n$ item *types* with weight $w\_i$ and quality $q\_i$ solve:

$$maximize \sum\_{i=1}^n q\_ix\_i $$ with:
$$ \sum\_{i=1}^n w\_ix\_i < W\\
x\_i >= 0\ \in N
$$
i.e. fill up the knapsack as much as possible (up to W) with items, the items are not limited in numbers, you have an unbounded number of copies of item1 with weight $w\_1$, and quality $q\_1$, etc. So the variable $x\_i$ are integers that denote how many copies of item $i$ are in a solution.

(2) The k-exact version of the above add another constraint:

$$ \sum\_{i=1}^n x\_i = k $$

i.e. you must take exactly $k$ item in total.

I do not need an algorithm for the problems, but I'd like to have an explicit reduction from (1) to (2). For a fixed istance of (1) the maximum number of items in a solution is limited from above by $kmax = W / \min w\_i$. Then I can solve (2) for all value of $k$ from $1$ to $kmax$ and take the maximum of the solutions, but I'd like to see if there is a better way or not.

**Tags:** np-hardness, reductions

> **Comments:**
> **username_1**: Can you please make your question self-contained by defining the problems you are talking about precisely.  
> **username_0**: Done. I also added more details on what I need. Thanks.  

---

## 0 answers

