Variaciones de LIS | DP-21

Hemos discutido la solución de programación dinámica para el problema de la subsecuencia creciente más larga en esta publicación y una solución O (nLogn) en esta publicación. Las siguientes son variaciones comúnmente solicitadas del problema LIS estándar . 

1. Construyendo puentes: Considere un mapa 2-D con un río horizontal que pasa por su centro. Hay n ciudades en la orilla sur con coordenadas x a(1) … a(n) y n ciudades en la orilla norte con coordenadas x b(1) … b(n). Desea conectar tantos pares de ciudades norte-sur como sea posible con puentes de modo que no se crucen dos puentes. Al conectar ciudades, solo puede conectar la ciudad i en la orilla norte con la ciudad i en la orilla sur. 

8     1     4     3     5     2     6     7  
<---- Cities on the other bank of river---->
--------------------------------------------
  <--------------- River--------------->
--------------------------------------------
1     2     3     4     5     6     7     8
<------- Cities on one bank of river------->

Fuente: Problemas prácticos de programación dinámica . El enlace también tiene una solución bien explicada para el problema. 
La solución para este problema ha sido publicada aquí . 

2. Subsecuencia Creciente de Suma Máxima: Dada una array de n enteros positivos. Escriba un programa para encontrar la subsecuencia de suma máxima de la array dada de manera que los enteros en la subsecuencia se clasifiquen en orden creciente. Por ejemplo, si la entrada es {1, 101, 2, 3, 100, 4, 5}, la salida debería ser {1, 2, 3, 100}. La solución a este problema ha sido publicada aquí . 

3. La string más larga Te dan pares de números. En un par, el primer número es más pequeño con respecto al segundo número. Suponga que tiene dos conjuntos (a, b) y (c, d), el segundo conjunto puede seguir al primero si b < c. Entonces puedes formar una string larga de manera similar. Encuentra la string más larga que se puede formar. La solución a este problema ha sido publicada aquí . 

4. Apilamiento de cajas Se le da un conjunto de n tipos de cajas tridimensionales rectangulares, donde la i^-ésima caja tiene altura h(i), ancho w(i) y profundidad d(i) (todos 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 base 2-D. D base de la caja superior. Por supuesto, puede rotar una caja para que cualquier lado funcione como su base. También está permitido usar varias instancias del mismo tipo de caja. 
Fuente: Problemas prácticos de programación dinámica . El enlace también tiene una solución bien explicada para el problema. 

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.