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}&lt;w_{i2}&lt;\cdots&lt;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?)
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)$.