Let us consider the following problem:
\begin{align} \max &\quad\sum_{i=1}^n\sum_{j=1}^m v_{i,j}\cdot x_{i,j} \\ \text{s.t.}&\quad \sum_{i=1}^n x_{i,j} =1 &\forall j =1,\dots,m \\ &\quad \sum_{i=1}^n\sum_{j=1}^m w_i\cdot x_{i,j} = W & \\ &\quad x_{i,j} \in \mathbb{B} &\forall i =1,\dots,n,\quad \forall j =1,\dots,m \end{align}
I would like to prove that this problem is NP-hard. I know that the multiple choice knapsack problem is NP-hard. However, there are two substantial differences with our problem:
- The weights of all item within a class are equal (i.e. we have $w_i$ instead of $w_{i,j}$).
- The capacity constraint must be satisfied by equality.
Therefore, my problem is a special case of the multiple choice knapsack problem, or: multiple choice knapsack problem is a generalisation of my problem. Therefore, I suspect that I can not reduce my problem from the multiple choice knapsack problem.
Still, I strongly suspect that the problem above is NP-hard. Am I missing something?