On Two Class-Constrained Versions of the Multiple Knapsack Problem

We study two variants of the classic knapsack problem, in which we need to place items of different types in multiple knapsacks; each knapsack has a limited capacity, and a bound on the number of different types of items it can hold: in the class-constrained multiple knapsack problem (CMKP) we wish to maximize the total number of packed items; in the fair placement problem (FPP) our goal is to place the same (large) portion from each set. We look for a perfect placement, in which both problems are solved optimally. We first show that the two problems are NP-hard; we then consider some special cases, where a perfect placement exists and can be found in polynomial time. For other cases, we give approximate solutions. Finally, we give a nearly optimal solution for the CMKP. Our results for the CMKP and the FPP are shown to provide efficient solutions for two fundamental problems arising in multimedia storage subsystems. Received June 1, 1998; revised December 5, 1998.