AkinaЕсли необходимо именно оптимальное решение - то это полный перебор. Т.е. решение задачи максимально равномерного распределения при заданном количестве сумок для каждого возможного количества сумок, и выбор наилучшего из решений.

Теперь это называется оптимальным решением ?

Учитывая сложность полного перебора, скорее следует говорить о том, что данный метод очевидно корректен, и гарантированно даёт результат. Термин "оптимальный" в данном конкретном случае не подходит

Михаил Ч.Реализация метода Гомори значительно сложнее полного перебора, но время затрачиваемое на решение задачи существенно меньше.
Полный перебор практически не применим в реальных условиях (с реальными данными).

Либо Вы имеете в виду не сложность реализации алгоритма, а асимптотическую сложность?

А в чём измеряется сложность реализации алгоритма ?))) Да, он имеет ввиду асимптотическую сложность конечно, но говорить о том какая сложность у данного алгоритма нет смысла, ибо число ограничений сильно влияет на итоговый результат. Я таких формул не встречал, есть оценка для одной итерации, но количество итераций(сколько ограничений будет в итоге) предсказать трудно.


Akina Вы хотите сказать, что сложность решения задачи линейного раскроя методом Гомори - лучше полиномиальной?

А вы сами как считаете ?

MasterZivSashaMercuryпропущено...


Теперь это называется оптимальным решением ?

Саша, опять ощущение, что Лейзерсон тебе просто прописан как лекарство.
Читай, это хорошая книга, и ,в от произведений Кнута, реально полезная.

И что он пишет про оптимальное решение ? У вас слишком абстрактный ответ.