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

Question

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

Вам дан набор из n типов прямоугольных трехмерных блоков, где я^ поле имеет высоту h (i), ширину w (i) и глубину d (i) (все действительные числа).Вы хотите создать стопку коробок, которая будет как можно более высокой, но вы можете сложить коробку только над другой коробкой, если размеры двухмерной базы нижнего прямоугольника строго превышают размеры двухмерной.Буду основанием верхней коробки.Конечно, вы можете вращать коробку так, чтобы любая сторона функционировала как ее основа.Также допустимо использовать несколько экземпляров одного и того же типа ящика.

Эта проблема кажется мне слишком сложной, чтобы понять шаги.Поскольку это 3D, я получаю три последовательности высоты, ширины и глубины.Но так как возможно обменять 3 измерения, проблема становится для меня более сложной.Поэтому, пожалуйста, кто-нибудь объяснит шаги для решения проблемы, когда нет обмена, а затем, как это сделать при обмене.Я устал от этой проблемы.Поэтому, пожалуйста, пожалуйста, кто-нибудь объяснит решение простым способом.

Answer 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/

Answer 2

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

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

Answer 3

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

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

тот же принцип, применяемый в трехмерном сценарии, только теперь вы НЕ МОЖЕТЕ просто умножить размер коллекции на 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.

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

Answer 4

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

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

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

Answer 5

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

This (Я думаю, что это базовый подход).

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

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

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