0-1 Multi-constraint Knapsack problem (MCKP) is an extension of Knapsack problem, where we have multiple constraints (for example we may have a volume limit and weight limit, where the volume and the weight of each item is not related). If there are m constraints, we may consider that there are m knapsacks, each with capacity of Wj. There are n items and weight of item i in knapsack j is defined as ??,? When we select an item, we may imagine that we insert a copy of it to all the knapsacks simultaneously (although we have a single instance from each item). (Note again that items weights are typically not same for different knapsacks).