Dimanchik писал(а):
Добрый день.
Может кто-нибудь знает точный алгоритм для обобщенной задаче о назначениях (generalized assignment problem)?
Вкратце о задаче:
Есть N предметов и M рюкзаков.
Pij = полезность i-го предмета в j-ом рюкзаке
Wij = вес i-го предмета в j-ом рюкзаке
Cj - вместимость j-го рюкзака
Необходимо раскидать предметы по рюкзакам так, чтобы получить максимальную полезность и
не превысить допустимый вес каждого рюкзака.
Есть точные алгоритмы Ross and Soland, MArtello and Toth и др. но все они были находятся в платном доступе (30 баксов за статью в pdf)
Может есть отечественные наработки в этом направлении или есть переведенные книги, где описан алгоритм ?
Я, честно говоря, в этом деле мало о чём знаю, но задача очень похожа на одну из стандартных задач линейного программирования, для решения которых используется симплекс метод.
16.04.2006, 19:44 
