# Knapsack with fixed size and flexible profit

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?

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.