We study two variants of the classic knapsack problem, in which
we need to place items of {\em 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 {\em class-constrained
multiple knapsack problem (CMKP)} we wish to maximize the total number of
packed items; in the {\em fair placement problem (FPP)} our goal is to
place the same (large) portion from each set. We look for a {\em 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
sub-systems.