Задача упаковки прямоугольников: точный алгоритм на базе матричного представления

Abstract

Рассматривается NP-трудная задача упаковки прямоугольников в полубесконечную полосу, которая имеет широкое применение в промышленности. Рассматривается матричное представление прямоугольной упаковки и ее различные свойства, которые позволяют создать эффективный алгоритм. Алгоритм трансформируется на задачу упаковки n-мерных параллелепипедов.