Число оборотов для коробки в блоке Укладка (DP) алгоритм 3 или 6?

Question

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

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

online resource В качестве способа создания трех ориентаций (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 будут разными, исходный алгоритм считает их sam.

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

Answer 1

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

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

Другими словами, учитывая коробку с размерами х> у> г, мы будем рассматривать ориентации:

ч = х, л = у, ш = г
ч = у, л = х, ш = г
ч = г, л = х, ш = у

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

ч = х, л = г, ш = у
ч = у, л = г, ш = х
ч = г, L = Y, W = х

Это просто, чтобы упростить представление коробки.
Даже в ссылке, которую вы указали они написали,
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 конфигурации.