Количество оборотов для ящика в алгоритме укладки ящиков (DP) равно 3 или 6?

Question

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

Однако я не смог понять, почему для каждой коробки требуется только 3 ориентации. По мне, количество ориентаций должно быть 6. То есть, для каждого из трех измерений, взятых за высоту, у вас должно быть две комбинации.

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

/* Create an array of all rotations of given boxes
      For example, for a box {1, 2, 3}, we consider three
      instances{{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} */
   Box rot[3*n];
   int index = 0;
   for (int i = 0; i < n; i++)
   {
      // Copy the original box
      rot[index] = arr[i];
      index++;

      // First rotation of box
      rot[index].h = arr[i].w;
      rot[index].d = max(arr[i].h, arr[i].d);
      rot[index].w = min(arr[i].h, arr[i].d);
      index++;

      // Second rotation of box
      rot[index].h = arr[i].d;
      rot[index].d = max(arr[i].h, arr[i].w);
      rot[index].w = min(arr[i].h, arr[i].w);
      index++;
   }

Так, например, для бокса {1, 2, 3} три ориентации будут

1 2 3
2 1 3
3 1 2

Но, по моему мнению, ориентация должна быть

1 2 3
1 3 2

2 1 3
2 3 1

3 1 2
3 2 1

Я понимаю, что мои дополнительные три комбинации происходят из-за чередования длины и ширины между ними, сохраняя высоту одинаковой. Итак, хотя я считаю, что 1 2 3 и 1 3 2 отличаются, оригинальный алгоритм считает их самими.

Тем не менее, я чувствую, что в этой задаче h, l, w и h, w, l должны рассматриваться как две отдельные ориентации, так как блок говорит, что l=3,w=4,h=5 может располагаться над блоком скажем, l = 4, w = 5, h = 6, но не выше прямоугольника l = 5, w = 4, h = 6

Answer 1

То, что вы сказали, абсолютно правильно, мы могли бы взять 6 ориентаций коробки, но дело в том, что мы можем обойтись только с 3 ориентациями коробки.

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

Другими словами, учитывая поле с размерами x > y > z, мы рассмотрим ориентации:

h = x, l = y, w = z
h = y, l = x, w = z
h = z, l = x, w = y

Но не такие ориентации, как:

h = x, l = z, w = y
h = y, l = z, w = x
h = z, l = y, w = x

Это просто для упрощения представления коробок.
Даже в указанной вами ссылке они написали:
for simplicity of solution, always keep w<=d:

struct Box
{
  // h –> height, w –> width, d –> depth
  int h, w, d;  // for simplicity of solution, always keep w <= d
};

Теперь, когда мы наложили это ограничение на данные, мы можем видеть, что ваша исходная проблема была решена, т.е.

Тем не менее, я чувствую, что в этой задаче h, l, w и h, w, l должны рассматриваться как две отдельные ориентации, так как блок говорит, что l=3,w=4,h=5 может располагаться над блоком скажем, l=4,w=5,h=6, но не выше прямоугольника l=5,w=4,h=6

Например, если было две коробки

h1,w1,l1 (Box1) и
h2,w2,l2 (Box2)

мы знаем w1<l1(потому что мы наложили это ограничение), так что если случайно w1>w2 мы знаем автоматически l1> w2и, следовательно, другой конфигурации коробки (где вы сказали, w а также l следует поменять местами и рассматривать как отдельную конфигурацию) не требуется.

Подумайте об этом, я уверен, вы поймете, почему мы используем только 3 конфигурации.