2
$\begingroup$

The multiple choice knapsack problem (MCKP) can be defined as follows:

enter image description here

MCKP is known to be NP-hard in general. I have a special case of MCKP for which

  • $N_i=\{1,2,\cdots,|N_i|\}$, for all $1\leqslant i\leqslant k$ ;
  • $p_{ij}=j$, for all $1\leqslant i\leqslant k$ and for all $1\leqslant j\leqslant|N_i|$; and
  • $w_{i1}<w_{i2}<\cdots<w_{i|N_i|}$, for all $1\leqslant i\leqslant k$.

My question is: Can we solve this special case of MCKP in polytime? (Or, is this special case of MCKP NP-hard?)

$\endgroup$
2
$\begingroup$

There is a dynamic programming solution.

Let $f(i, V)$ be the minimum weight to achieve value $V$ while only the first $i$ classes (i.e. $N_1,\ldots,N_i$) are considered, then according to the item to be chosen in $N_{i+1}$, we have

$$ f(i+1,V)=\min_{0\le j\le |N_i|}w_{ij}+f(i,V-j), $$

where $w_{i0}$ is defined to be 0. Now you can compute $f(n,1),\ldots,f(n,\sum_{i=1}^n |N_i|)$ to get the first $j$ such that $f(n,j)\le W$, then this $j$ is an optimal value for your original problem.

This algorithm runs in $$ O\left(\left(\sum_{i=1}^n |N_i|\right)^2\right). $$

This is polytime because the input length is $\Theta\left(\sum_{i=1}^n |N_i|\right)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.