1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.