# A Special Case of Multiple Choice Knapsack Problem: Is it NP-hard?

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

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?)

## 1 Answer

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)$.