Аппроксимационные схемы для задачи об упаковке в контейнеры: различия между версиями

В [[задача об упаковке в контейнеры|задаче об упаковке в контейнеры]] входными данными является набор предметов, определяемых их размерами. Также имеются одинаковые контейнеры, размеры которых без потери общности можно считать равным 1. Цель состоит в том, чтобы упаковать заданные предметы, используя минимально возможное количество контейнеров.

Упаковка контейнеров является классической оптимизационной задачей, и сотни ее вариантов были определены и изучены для различных условий, таких как анализ среднего случая, анализ наихудшего случая в оффлайновом режиме и анализ наихудшего случая в онлайновом режиме. Далее рассматривается самый простой вариант, упомянутый выше, в рамках оффлайновой модели, когда все предметы заданы заранее. Легко убедиться, что эта задача является NP-полной, с помощью редукции задачи разбиения. Фактически такая редукция означает, что за исключением случая P = NP невозможно за полиномиальное время определить, можно ли упаковать предметы в два контейнера или их нужно будет три.