2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you please make your question self-contained by defining the problems you are talking about precisely. $\endgroup$ – Jan Johannsen Feb 23 '17 at 17:23
  • $\begingroup$ Done. I also added more details on what I need. Thanks. $\endgroup$ – Antonio Caruso Feb 23 '17 at 19:47
  • $\begingroup$ Set ​ $k = \lfloor kmax\rfloor$ , ​ then create a new item whose $q$ and $w$ are both zero. ​ ​ ​ ​ $\endgroup$ – user6973 Feb 26 '17 at 4:54

Your Answer

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

Browse other questions tagged or ask your own question.