serendpt

دوستان میشه بگید الگوریتم حل این سوال چی هست؟
In the 0-1 Multiple Knapsack Problem (MKP) a set of n items and a set of m knapsacks (with m  n)
are given. With each item j (j = 1; : : : ; n) are associated a prot pj 2 Z+ and a weight wj (we assume
wj 2 Z+). A capacity ci 2 Z+ is associated with each knapsack i (i = 1; : : : ;m). The goal is to select
is to select m disjoint subsets of items so that the total prot of the selected items is maximum and
each subset can be assigned to a dierent knapsack whose capacity is no less than the total weight of
the items in the subset.

Develop a heuristic algorithm based on the Lagrangian relaxation of constraints