Article ID: | iaor20121014 |
Volume: | 29 |
Issue: | 3 |
Start Page Number: | 442 |
End Page Number: | 467 |
Publication Date: | Mar 2001 |
Journal: | Algorithmica |
Authors: | Shachnai H, Tamir T |
Keywords: | knapsack problem, multimedia, NP-hard |
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