Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We have $3n$ items with profits $p_1, \dots, p_{3n}$ (sum = $P$) and weights $w_1,\dots,w_{3n}$ (sum = $W$). We want to determine whether we can choose exactly $n$ items with profit at least $P/2$ and weight at most $W/2$.
Is this problem NP-hard? It is very similar to the usual knapsack problem, but the constraint of choosing exactly $n$ items makes it difficult to reduce directly from knapsack.
The problem is NP-Hard. You can reduce from the partition problem: given a multi-set $X = \{x_1, \dots, x_n\}$ of non-negative integers, is there a subset $S$ of $X$ such that $\sum_{x \in S} x = \frac{1}{2} \sum_{x \in X} x$?
To obtain an instance of your problem you can create one $y_i$ for each integer $x_i$ and set $p_i = w_i = x_i$. Then create $2n$ additional "dummy" items with weight 0 and profit 0.
If there is a solution $S = \{x_{i_1}, \dots, x_{i_k}\}$ to the partition instance, then you can obtain a solution to your problem by selecting the items $y_{i_1}, \dots, y_{i_k}$ plus $n-k$ dummy items.
If there is a solution to the instance of your problem with non-dummy items $y_{i_1}, \dots, y_{i_k}$ (and any number of dummy items) both the total weight and the total profit of the selected items must be exactly $\frac{1}{2} \sum_{x \in X} x$. Then, the set $S = \{x_{i_1}, \dots, x_{i_k}\}$ is a solution for the partition instance.
