I am working on the following exercise: Prove that if $ P \neq NP$ , there cannot exist an approximation algorithm $ A$ for the knapsack problem (KP) such that $ \exists k \in \mathbb{N}, \forall I \in S: OPT(I) – P_A(I) \leq k$ where $ OPT(I)$ is the optimal profit on instance $ I$ and $ P_A(I)$ is the profit calculated by $ A$ .

I know that there is a FPTAS $ A’$ for the KP which guarantees a solution with profit $ P_{A’}(I) \geq (1 – \varepsilon)OPT(I)$ on any instance $ I$ and $ \varepsilon > 0$ .

My approach is to create a contradiction. For this I consider $ A = A’$ and aim to show that $ P_A(I) \geq (1 – \varepsilon)OPT(I) \geq … \geq OPT(I) – c$ where $ c \in (0,1)$ is a constant. This way, for an adequate choice of $ \varepsilon$ I would show that we obtain an optimal solution within polynomial time. However, I struggle how to choose $ \varepsilon$ .

I need some advice on how to proceed. Many thanks in advance!