# 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

## 1 Answer

I think the problem is NP-hard since:

1. it will reduce to the 0-1 Knapsack problem with an equality constraint; and,

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

So, your problem is NP-hard as 0-1 Knapsack is.

P.S. To see why (2) is correct, suppose all weights and values are equal. Then the problem reduces to the subset sum problem, that is also NP-hard.

• Thank you very much for answering my question. Could you perhaps explain why changing ≤ to = does not change the complexity? I could not find a source stating that knapsack with equality sign is NP-hard. – Pete S Feb 6 at 14:01
• Yes, I edit the post. – Mostafa Feb 6 at 14:45