# NP-hardness of a special case of multiple choice knapsack problem

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:

1. The weights of all item within a class are equal (i.e. we have $$w_i$$ instead of $$w_{i,j}$$).
2. 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?

• I think you mean $x_{i,j}\in\Bbb N$. – TheSimpliFire Feb 7 at 10:35
• @TheSimpliFire The first constraint set forces $x_{i,j}$ to be binary. – Mostafa Feb 7 at 13:01
• @Mostafa Of course, my mistake. – TheSimpliFire Feb 9 at 11:26

2. changing $$\leq$$ to $$=$$ in the 0-1 Knapsack constraint does not change its complexity (see explanation below).