The 0 – 1 Knapsack Problem An Introductory Survey
The 0–1 Knapsack problem has been studied extensively during the past four decades. The reason is that it appears in many real domains with practical importance. Although its NP-completeness, many algorithms have been proposed that exhibit impressive behavior in the average case. This paper introduces the problem and presents a proof that it belongs to the NP-complete class, as well as a list of directly related problems. An overview of the previous research and the most known algorithms for solving it are presented. The paper concludes with a reference to the practical situations where the problem arises.