apilamiento de cajas en la teoría de grafos

Question

Por favor, ayúdenme a encontrar una buena solución para este problema.

Tenemos n cajas con 3 dimensiones. Podemos orientarlos y queremos ponerlos encima de otro para tener una altura máxima. Podemos poner una caja encima de otra caja, si 2 dimensiones (ancho y largo) son más bajas que las dimensiones de la casilla a continuación.

Por ejemplo tenemos 3 dimensiones w * D * h, podemos mostrarlo en (h * d, d * h, w * d, d * W, h * w, w * h) por favor ayuda yo para resolverlo en la teoría de grafos. en este problema no podemos poner (2 * 3) arriba (2 * 4) porque tiene el mismo ancho. Así que la 2 dimensión debería ser más pequeña que la caja

Answer 1

ACTUALIZADO (¿correcto? Pero posiblemente no el más eficiente):

Cada cuadro se convierte en 3 vértices (llame a estos vértices relacionados). Obtenga un DAG ponderado. Modifique el algoritmo descrito here Ordene topológicamente (ignorando el hecho de que algunos vértices están relacionados), siga el algoritmo pero en lugar de una matriz de enteros, mantenga una lista de las rutas que conducen a cada vértice. Luego, cuando se agreguen rutas para un nuevo vértice ('w' en wiki alg), haga una lista de las rutas que llevan allí al eliminar las rutas a v que contienen un vértice relacionado con w. A diferencia del algoritmo original, este es exponencial.

respuesta equivocada ORIGINAL (ver comentarios):

Cada caja se convierte en 3 nodos para sus 3 tamaños de superficie. Luego, cree un gráfico dirigido que conecte cada superficie a todas las superficies de tamaños más pequeños. Asigne un precio a cada borde para que sea igual a la 3ª dimensión del nodo (es decir, altura) a la que conduce el borde. Ahora este es el problema de encontrar el longest path problem in a DAG.

Answer 2

Editar: Solo funciona si las cajas no se pueden girar en todos los ejes.

Si entiendo la pregunta correctamente, puede resolverse mediante programación dinámica. Un algoritmo sencillo para encontrar la altura de la pila máxima es:

Comience por rotar todas las casillas de forma que para la casilla B_i, w_i < = d_i. Esto lleva tiempo O (n).

Ahora ordene las casillas de acuerdo con el área inferior w_i * d_i y deje que la indexación lo muestre. Esto lleva tiempo O (n log n).

Ahora B_i se puede poner en B_j solo si i < j, pero i < j no implica que B_i pueda estar en B_j.

La pila más grande con B_j en la parte superior es o bien

• B_j en el suelo
• Una pila hecha de los primeros j-1 cajas, con B_j en la parte superior.

Ahora podemos crear una fórmula recursiva para el cálculo de la altura de la pila máxima

H (j) = max (h_j, max (H (i) | i < j, D_I < D_j, w_i < w_j) + h_j)

y calculando max (H (j), i < = j < = n) obtenemos la altura de la pila máxima.

Si queremos la pila real, podemos adjuntar cierta información a la función H y recordar los índices.