Re: Упаковка в несколько рюкзаков
От: Аноним  
Дата: 10.06.11 08:21
Оценка:
Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>Помогите разобраться к какому классу относиться задача и куда смотреть.


HTB>Есть несколько «рюкзаков» (3) есть несколько грузов с разным весом (~10).

HTB>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

Частный случай этой задачи (когда груз возможно распределить ровно) является сильно NP-полной(т.е. не существует псевдополимиальных алгоритмов).
http://en.wikipedia.org/wiki/3-partition_problem

Отсюда можно предположить, что для точного ответа потребуется перебрать все варианты. Учитывая что их всего 60000 (3^10), пока не вижу смысла копать глубже.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.