задачи упаковки

Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную , в которой спрашивается, как много требуется некоторых предметов, чтобы полностью покрыть все области контейнера, при этом предметы могут накладываться. В задаче упаковки задано: * «контейнеры» (обычно одна двумерная или трёхмерная выпуклая область или бесконечная область) * множество «объектов», некоторые из которых или все должны быть упакованы в один или несколько контейнеров. Множество может содержать различные объекты с заданными размерами, или один объект фиксированных размеров, который может быть использован несколько раз. Обычно в упаковке объекты не должны пересекаться и объекты не должны пересекать стены контейнера. В некоторых вариантах цель заключается в нахождении конфигурации, которая упаковывает один контейнер с максимальной плотностью. В более общем виде целью является упаковка всех объектов в как можно меньше контейнеров. В некоторых вариантах наложение (объектов друг на друга и/или на границы контейнера) разрешается, но это наложение должно быть минимизировано.