Есть множество из n прямоугольников размера wi x hi. Требуется разместить их в минимальном количестве прямоугольников фиксированного размера W x H так, чтобы прямоугольники из исходного множества не накладывались друг на друга. В итоговом размещении прямоугольники могут быть как угодно повернуты, главное — чтобы они не накладывались друг на друга.
Размеры прямоугольников, вообще говоря, могут быть вещественными числами, но можно рассматривать и целочисленный вариант задачи. Также для простоты можно рассмотреть случай, когда допустимы только те размещения, в которых стороны размещаемых прямоугольников параллельны сторонам прямоугольников — контейнеров.
Источник — задача из жизни соответствующего содержания. Есть множество прямоугольных панелей стандартного размера, из них вырезаются нестандартные прямоугольные детали произвольных размеров. Известно, какие детали нужно получить, ну и требуется затратить на это минимальное количество исходных стандартных панелей.
Интуиция и знакомство с отдаленно похожей задачей на тимусе намекает, что данная задача NP-трудная. Поэтому был бы рад услышать любую идею и о приближенном алгоритме. Сам навскидку придумал пару эвристик, но что-то они не выглядят достаточно эффективными.
Заранее спасибо всем!
