A minimal algorithm for the Multiple-Choice Knapsack Problem

The Multiple-Choice Knapsack Problem is defined as a 0–1 Knapsack Problem with the addition of disjoined multiple-choice constraints. As for other knapsack problems most of the computational effort in the solution of these problems is used for sorting and reduction. But although O(n) algorithms which solve the linear Multiple-Choice Knapsack Problem without sorting have been known for more than a decade, such techniques have not been used in enumerative algorithms. In this paper we present a simple O(n) partitioning algorithm for deriving the optimal linear solution, and show how it may be incorporated in a dynamic programming algorithm such that a minimal number of classes are enumerated, sorted and reduced. Computational experiments indicate that this approach leads to a very efficient algorithm which outperforms any known algorithm for the problem.