Проблема с укладкой коробки

Ответ 1

Я думаю, вы можете решить эту проблему с помощью алгоритма динамического программирования с наибольшим возрастанием подпоследовательности: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Учет поворотов достаточно прост: для каждой башни все, что вам нужно проверить, - это то, что происходит, если вы используете ее высоту как длину основания и ширину, как высоту, и что происходит, если вы используете ее естественным образом, Например:

=============
=           =
=           =
=           = L
=     H     =
=           =
=           =
=============   
      W

Становится чем-то вроде (да, я знаю, что это выглядит не так, как должно, просто следуйте за обозначениями):

==================
=                =
=                =  
=       W        = L
=                =
=                =
==================
        H

Итак, для каждого блока у вас на самом деле есть 3 блока, представляющих его возможные вращения. Отрегулируйте массив блоков в соответствии с этим, затем отсортируйте, уменьшив базовую область и просто примените алгоритм DP LIS для получения максимальной высоты.

Адаптированный рекуррент: D [i] = максимальная высота, которую мы можем получить, если последняя башня должна быть i.

D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

Смотрите видео, объясняющее это здесь: http://people.csail.mit.edu/bdean/6.046/dp/

Ответ 2

Стек можно рассматривать как последовательность x, y, z triplets (x, y - двумерная плоскость, а z - высота), где x (i) > x (i + 1) и y (i) > y (i + 1). Цель состоит в том, чтобы максимизировать сумму z, собирающую триплеты из набора доступных триплетов - каждый триплет является одним типом коробки в определенной ориентации. Довольно легко понять, что принудительное ограничение x > y не уменьшает пространство решений. Таким образом, каждый ящик генерирует 3 триплета, каждый из которых w, h, d в качестве координаты z.

Если вы рассматриваете триплеты как ориентированный ациклический граф, где ребра длины z существуют между двумя триплетами, когда ограничения x, y удовлетворяются между ними, тогда проблема заключается в поиске самого длинного пути через этот граф.

Ответ 3

Сначала попытаемся решить эту проблему в 2-D:

говорят, что у вас есть прямоугольники с X и Y, и вопрос подобен (самая высокая башня, но на этот раз вам нужно только беспокоиться об одном базовом измерении).
поэтому сначала вы просматриваете всю коллекцию, дублируя каждый прямоугольник, поворачивая ее на 90 градусов (заменяя X и Y), за исключением квадратов (где X (1) = X (2) & Y (1) = Y ( 2)). это представляет все возможные варианты.
то вы сортируете их по их X-стороне, от самой большой до самой маленькой. в случае дублирования значения X вы удаляете значение с более низким значением Y.

тот же принцип применяется в трехмерном сценарии, только теперь вы DONT просто умножаете размер коллекции на 6 (все возможные варианты W, H, D), а скорее на 2. вы делаете это, отклоняя все варианты, где ширина ниже глубины (поэтому для каждого i, W (i) >= D (i)), а затем отклонения вариации, где высота не является самой высокой и самой низкой из трех измерений (поскольку другие два варианта могут идти один поверх другого, и к этому нельзя присоединиться). опять же, вы также отклоняете дублирование (где W (1) = W (2) & H (1) = H (2) & D (1) = D (2)). Затем вы должны сортировать по ширине, только на этот раз вы не выбрасываете вариации с одинаковой шириной (потому что один может поместиться в башню, а другой нет), тогда вы можете использовать алгоритм LIS, как описано выше, @IVlad:

D[1] = h(1);
D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.

трюк был, вы знаете, что ширина является самой длинной из двух, поэтому вы знаете, что первый элемент не будет помещен поверх любого более позднего элемента.

Ответ 4

Я предлагаю вам создать дерево (или какую-то древовидную структуру) и проанализировать его с помощью поиска глубины, вычисляя максимальную высоту от отдельных значений вертикальной высоты (от поворота на поворот).

Это (я думаю, что это основной подход).

Подробности по деталям:

Корнем дерева должен быть пол, где любой куб подходит. Оттуда вы просто создаете дочерние узлы возможных следующих (коробки, которые могут быть помещены в определенное вращение на вершине текущего окна). Рекурсивно сделайте это для каждой коробки и вращения.

Когда дерево будет построено, пройдите через него и вычислите общую высоту башни от пола до листа дерева.

Ответ 5

Решение проблемы состоит из трех шагов.

• Сортировать размеры для каждого окна, чтобы сравнить любые два блока, чтобы сравнить их соответствующие размеры.
• Сортируйте последовательность ящиков лексикографически так, чтобы для каждого поля поля слева были полями, которые могут соответствовать.
• Примените алгоритм O(n^2) для самой долговечной проблемы послепоследовательности.

Третий шаг - самый дорогой и затрудняет сложность решения O(n^2). Если вы хотите прочитать полное объяснение подхода, как каждый шаг способствует поиску ответа и полному коду, посмотрите сообщение в блоге, которое я написал о проблеме.