Ajuste un conjunto de bloques rectangulares dados en orden aleatorio en una caja de volumen mínimo

Question

Dado un conjunto de bloques cuya longitud, anchura y altura, respectivamente, son $A:1 \times 3 \times 2$, $B: 2 \times 2 \times 1$, $C \text{ and } D: 2 \times 1 \times 1$, y $E,F,G\text{ and }H: 1 \times 1 \times 1$. Los bloques se pueden girar en cualquier dirección, pero no puede ser reemplazado una vez establecidas.

Si tenemos control sobre el orden de los bloques entrega a nosotros, podemos, por ejemplo, la pila de todas las cajas en un $3 \times 3 \times 2$ cuadro, como se muestra en la siguiente imagen, una solución óptima: Supongamos ahora que no tenemos ningún control sobre el orden de los bloques entrega a nosotros, y no podemos mover los bloques, una vez colocados, ¿cuál es el volumen más pequeño cuadro que las garantías para adaptarse a todos los bloques? Un evidente límite superior es colocar todas las cajas en una sola capa, pero el resultado será mucho espacio desaprovechado.

También podría ser demasiado difícil encontrar el exacto volumen más pequeño, pero la solución mejorado la obvia límite superior es bienvenida.

Mi intuición es que usted necesita para dividir los bloques en un par de grupos, la colocación de cada grupo es independiente de los otros grupos, y dentro de cada uno de los grupos, el total de espacio ocupado es el mismo para cualquier pedido dentro del grupo. Uno de esos grupos podría ser $C$ e $D$, ya que el volumen de apilamiento de estos $2$ es el mismo independientemente de que aparece el primero.

Actualizaciones: Inspirado por el aceptado respuesta, encontré estas soluciones óptimas para el problema:

1. Ordenar los elementos en la altura de la pila de 1:

AADDCF

AABBCG

AABBEH

2. Ordenar los elementos en la altura de la pila de 2:

Ver la aceptación respuesta

3. Ordenar los elementos en la altura de la pila de 3:

Asumir apilados producto de BC = X, apilados, producto de la DG = Y, apilados, producto de la EFH = Z

AXY

AXZ

4. Ordenar los elementos en la pila de altura>3:

Obviamente, para lograr una solución óptima, la altura de la pila sólo puede ser 6,9 y 18.

La altura de la pila de 6: Combinar ABC, y DEFGH

La altura de la pila de 9: No es posible

La altura de la pila de 18: No es posible

Answer 1

Corríjame si estoy interpretando el problema incorrectamente, pero creo que siempre puede lograr un empaque óptimo. Para hacerlo, construya este arreglo, que tiene una altura de$2$, y donde las X se refieren a pilas de dos bloques de$1 \times 1 ×1$.

 A C D
A X B
A X B
 

Cada bloque toca el piso, por lo que cada bloque puede colocarse cuando se le entrega (a excepción de los bloques superiores sobre las dos torres X, pero estos se colocan encima de los pequeños bloques anteriores).