Knapsack with fixed size and flexible profit

Question

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 - 1$ and weight at most $W/2$.

If the profit must be at least $P/2$, we can set the profits to be equal to the weights and reduce from the partition problem to show NP-hardness. With the requirement of profit slightly lowered to $P/2-1$, I think the problem should remain NP-hard, but the reduction doesn't work anymore. Is there a way to modify the reduction to work?

Answer 1

Let $\mathcal{I}$ be an instance of the problem with profit requirement at least $P(\mathcal{I})/2$, where $P(\mathcal{I}) = p_1+\dotsc+p_{3n}$. By the previous reduction, we know that the problem is $\mathsf{NP}$-hard. Moreover, the reduced hard instances had profits $p_i$ as non-negative integers. We will exploit this fact for our reduction.

We reduce the instance $\mathcal{I}$ to an instance $\mathcal{I}'$ with profit requirement at least $P(\mathcal{I}')/2-1$. The instance $\mathcal{I}'$ is the same as instance $\mathcal{I}$ but with each profit four times the original value. Therefore, we have $P(\mathcal{I}') = 4P(\mathcal{I})$

Claim: There exists a feasible solution for $\mathcal{I}$ iff there exists a feasible solution for $\mathcal{I}'$.

Proof: $(\to)$ Let $\{x_{i_1},\dotsc,x_{i_{n}}\}$ be a feasible solution of $\mathcal{I}$ with profit at least $P(\mathcal{I})/2$. Then, the same solution is a feasible solution of $\mathcal{I}'$ with profit at least $4P(\mathcal{I})/2 \geq 4P(\mathcal{I})/2 - 1 = P(\mathcal{I}')/2 - 1$.

$(\gets)$ Let $\{x_{i_1},\dotsc,x_{i_{n}}\}$ be a feasible solution of $\mathcal{I}'$ with profit at least $P(\mathcal{I}')/2-1 =2P(\mathcal{I}) - 1$. Since the profit values are all even integers, the cost of the solution must be at least $2P(\mathcal{I})$. Then, the same solution is a feasible solution of $\mathcal{I}$ with profit at least $P(\mathcal{I})/2$.

---

This proves that the problem with profit requirement at least $P/2-1$ is $\mathsf{NP}$-hard as well.