Задача об упаковке в контейнеры

Материал из Википедии — свободной энциклопедии

В теории сложности вычислений задача об упаковке в контейнеры — NP-трудная комбинаторная задача. Задача заключается в упаковке объектов различного объёма в конечное число контейнеров объёмом $V$ таким способом, чтобы число использованных контейнеров было наименьшим.

Существует множество разновидностей этой задачи (двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т.п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т.д.

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

Стратегии Best Fit Decreasing и First Fit Decreasing используют не более $\frac{11}{9}N + 1$ контейнеров (где $N$ - число контейнеров при наилучшем решении задачи). Однако, существуют алгоритмы приближения, которые могут решить задачу об упаковке с любым наперёд заданным процентом наилучшего решения для больших массивов исходных данных (они называются асимптотической схемой приближения полиномиального времени). Всё это выделяет задачу среди большинства других основных NP-трудных задач, некоторые из которых не могут быть приближены вообще.