Article Preview
Top1. Introduction
0-1 Multiple Knapsack Problem (MKP) is a generalization of the standard 0-1 Knapsack Problem (KP) where multiple knapsacks are required to be filled instead of one.
Given a set of n items with their profits pj and weights wj, 
. and m knapsacks with capacities ci,
. the MKP is to select a subset of items to fill given m knapsacks such that the total profit is maximized and sum of weights in each knapsack i doesn’t exceed its capacity ci.
maximize:
(1) subject to:
(2)(3)(4)where 
.= 1 if item j is assigned to knapsack i, 
.= 0 otherwise and coefficients pj, wj and ci are positive integers.
In order to avoid any trivial case, the following assumptions are made
- 1.
Every item has a chance to be placed at least in largest knapsack:
(5) - 2.
The smallest knapsack can be filled at least by the smallest item:
(6) - 3.
There is no knapsack which can be filled with all N items:
(7)
The subset sum variant of MKP having 
is known as Multiple Subset Sum Problem (MSSP).
The MKP have several applications. An application is seen when scheduling jobs on processors where some machines are unavailable for a fixed duration or some high priority jobs are pre-assigned to processors (Diedrich & Jansen, 2009). A real-world application of MKP is the problem of cargo loading where some containers need to be chosen from a set of n containers to be loaded in m vessels with different loading capacities for the shipment of the containers (Eilon & Christofides, 1971). Another real-world problem for MSSP is mentioned in (Kellerer, Pferschy, & Pisinger, 2004, p. 287) from a company producing objects of marble.
The MKP problem is strongly NP-complete. Some approximation algorithms exist for MKP. Kellerer (Kellerer H., 1999) presented a Polynomial Time Approximation Scheme for MKP with identical capacities. Chekuri & Khanna (Chekuri & Khanna, 2006) generalized it and presented the PTAS for MKP. However, no Fully Polynomial Time Approximation Scheme is possible for MKP (Chekuri & Khanna, 2006).