# Approximation scheme for Multiple Choice Knapsack

The paper _Fast Approximation Algorithms for Knapsack Problems (E. Lawler, 1979) gives an FPTAS (fully polynomial time approximation scheme) for the multiple choice knapsack problem (MKP). But MKP is strongly NP-hard, so it cannot have an FPTAS unless P=NP. Is the result of this paper wrong?

The paper you cite is not available to me. However, according to this paper: "Improved Fully Polynomial time Approximation Scheme for the 0-1 Multiple-choice Knapsack Problem",

0-1 MCKP is $\text{NP}$-hard [4] as it contains the 0-1 Knapsack problem as a special case [5, 13] but it can be solved in pseudo-polynomial time (emphasis added) through dynamic programming [7, 2].

Thus, 0-1 MCKP is not strongly $\text{NP}$-hard.

One of the citations is

[7] K. Dudzinski, S. Walukiewicz, “Exact Methods for the Knapsack Problem and its Generalizations”, European Journal of Operational Research, (28), (1987): 3–21.