В задаче прямоугольник упаковки, один дается набор прямоугольников и ограничивающий прямоугольник R . Задача состоит в том, чтобы найти расположение r 1 , … , r n внутри R так , чтобы ни один из n прямоугольников не перекрывался. Как правило, ориентация каждого прямоугольника г я фиксируется. То есть прямоугольники нельзя вращать. В этом случае, как известно, проблема является NP-полной (см., Например, Korp 2003 ).
В чем сложность проблемы упаковки прямоугольников, если прямоугольники можно повернуть на градусов?
Интуитивно понятно, что разрешение поворотов должно только усложнить задачу, поскольку сначала нужно выбрать ориентацию для каждого прямоугольника, а затем решить проблему упаковки без поворота. Но доказательство твердости NP в случае отсутствия вращения представляет собой сокращение от упаковки бина и, по-видимому, критически зависит от фиксированной ориентации каждого прямоугольника для построения бинов. Я не смог найти соответствующее доказательство твердости NP для случая, в котором разрешены вращения.
источник