algorithm - para - peligros y riesgos en almacenes
Problema de apilamiento de cajas (5)
Encontré este famoso problema de dp en muchos lugares, pero no puedo descubrir cómo resolverlo.
Se le proporciona un conjunto de n tipos de cuadros 3-D rectangulares, donde el cuadro i ^ th tiene la altura h (i), el ancho w (i) y la profundidad d (i) (todos los números reales). Desea crear una pila de cajas que sea lo más alta posible, pero solo puede apilar una caja encima de otra caja si las dimensiones de la base 2-D de la caja inferior son estrictamente mayores que las de la 2 D base de la caja superior. Por supuesto, puede rotar una caja para que cualquier lado funcione como su base. También es posible utilizar múltiples instancias del mismo tipo de caja.
Este problema me parece demasiado complicado para entender los pasos. Como es 3D, obtengo tres secuencias de altura, anchura y profundidad. Pero como es posible intercambiar 3 dimensiones, el problema se vuelve más complicado para mí. Entonces, por favor, alguien explica los pasos para resolver el problema cuando no hay intercambio y luego cómo hacerlo cuando se intercambia. Me cansé del problema. Así que por favor, por favor alguien explique la solución de manera fácil.
Creo que puede resolver esto utilizando el algoritmo de subsecuencia cada vez mayor más dinámico: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
La contabilidad de las rotaciones es bastante fácil: para cada torre, todo lo que tiene que verificar es qué sucede si usa su altura como la longitud de la base y su ancho como la altura y qué sucede si la usa de forma natural. Por ejemplo:
=============
= =
= =
= = L
= H =
= =
= =
=============
W
Se convierte en algo como (sí, sé que no se parece en nada a lo que debería, solo sigue las anotaciones):
==================
= =
= =
= W = L
= =
= =
==================
H
Entonces, para cada bloque realmente tiene 3 bloques que representan sus posibles rotaciones. Ajuste la matriz de bloques de acuerdo con esto, luego ordene disminuyendo el área base y solo aplique el algoritmo DP LIS para obtener la altura máxima.
La recurrencia adaptada es: D [i] = altura máxima que podemos obtener si la última torre debe ser 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.
Vea un video que explica esto aquí: http://people.csail.mit.edu/bdean/6.046/dp/
La pila puede considerarse como una secuencia de x, y, z tripletes (siendo x, y el plano 2D yz la altura), donde x (i)> x (i + 1) y y (i)> y ( i + 1). El objetivo es maximizar la suma de z seleccionando los tripletes del conjunto de tripletes disponibles, cada triplete es un tipo de caja en una orientación particular. Es bastante fácil ver que hacer cumplir la restricción x> y no reduce el espacio de la solución. Entonces, cada caja genera 3 tripletes, teniendo cada uno de w, h, d como la coordenada z.
Si considera los tripletes como un gráfico acíclico dirigido donde existen bordes de longitud z entre dos tripletes cuando las restricciones x, y se cumplen entre ellos, entonces el problema es encontrar el camino más largo a través de ese gráfico.
Le sugiero que cree un árbol (o algún tipo de estructura de árbol) y lo analice con la búsqueda en profundidad, calculando la altura máxima a partir de los valores individuales de "altura" vertical (dependiendo de la rotación).
Esto (creo que este es el enfoque básico).
Detalles sobre detalles:
La raíz del árbol debe ser el suelo, donde encaja cualquier cubo. A partir de ahí, simplemente crea los nodos secundarios de posibles cuadros siguientes (cuadros que se pueden colocar en una cierta rotación en la parte superior del cuadro actual). Recursivamente hacer eso para cada caja y rotación.
Cuando se construya el árbol, recórrelo y calcule la altura total de la torre desde el piso hasta una hoja del árbol.
Primero tratemos de resolver este problema en 2-D:
digamos que tienes rectángulos con X e Y, y la pregunta es similar (la torre más alta, pero esta vez solo tienes que preocuparte por una dimensión base).
así que primero, repase toda la colección, duplicando cada rectángulo girándolo 90 grados (intercambiando X e Y), excepto los cuadrados (donde X (1) = X (2) && Y (1) = Y (2)) . esto representa todas las variaciones posibles.
Luego las clasificas por su lado X, de mayor a menor. en caso de un valor X duplicado, elimine el valor Y más bajo.
Se aplica el mismo principio en el escenario tridimensional, solo que ahora NO multiplica el tamaño de la colección por 6 (todas las variantes posibles de W, H, D) sino por 2. lo hace descartando todas las variaciones donde el ancho es menor que la profundidad (entonces para cada i, W (i)> = D (i)), y luego descartar la variación donde la altura no es la más alta ni la más baja de las tres dimensiones (porque las otras dos variaciones pueden ir una en encima del otro y éste no puede unirse). de nuevo, también descarta las duplicaciones (donde W (1) = W (2) && H (1) = H (2) && D (1) = D (2)).
Entonces debe ordenar por ancho, solo que esta vez no puede tirar las variaciones con el mismo ancho (porque una puede caber en una torre que otra no) y luego puede usar el algoritmo LIS como se describe anteriormente en @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.
El truco fue que sabes que el ancho es el más largo de los dos, así que sabes que el primer elemento no encajará sobre ningún elemento posterior.
Una solución al problema consta de tres pasos.
- Ordene las dimensiones de cada cuadro de manera que la comparación de dos cuadros se reduzca a la comparación de sus dimensiones correspondientes.
- Ordene la secuencia de cajas lexicográficamente de manera que para cada caja, las cajas a la izquierda sean las que puedan caber.
- Aplique el algoritmo
O(n^2)para el problema de subsecuencia cada vez mayor .
El tercer paso es el más caro y aumenta la complejidad de la solución a O(n^2) . Si desea leer una explicación completa del enfoque, cómo cada paso contribuye a encontrar una respuesta y el código completo, consulte la publicación del blog que escribí sobre el problema .