How to solve a knapsack problem with increased weight limit?
-
04-11-2019 - |
Pergunta
Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the other has a weight limit of $W'=2W$. Assume that we have an optimal algorithm $\texttt{OPT}$ that solves the knapsack problem.
Let $O$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the first bin (that has a weight limit of $W$) and to the set of items $P$. Also, let $O'$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the second bin (that has a weight limit of $W'=2W$) and to the same set of items $P$.
Can we compare $O$ and $O'$?
I guessed that $$O'\leq 2O.$$
Nenhuma solução correta