As we know, an unbounded knapsack problem could be described as:

$\max \sum_{i=1}^nc_1x_i$

s.t. $\sum_{i=1}^na_ix_i\le b$

$x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$

And for an 0-1 knapsack problem, we have an additional restriction:


However, I would like to know whether there exists a reduction from the 0-1 knapsack problem to the unbounded knapsack problem?

I have thought over this problem, but I could not imagine whether something could be done in the unbounded problem in order to simulate the effect as the constraint $x_i\in\{0,1\}$ in a 0-1 knapsack problem.



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.