Programación Dinámica | 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 a(i) en la orilla norte con la ciudad b(i) en la orilla sur. Número máximo de puentes que se pueden construir para conectar pares norte-sur con las restricciones mencionadas anteriormente.
 

Los valores en el banco superior se pueden considerar como las coordenadas x del norte de las ciudades y los valores en el banco inferior se pueden considerar como las coordenadas x del sur correspondientes de las ciudades a las que se puede conectar la ciudad de coordenadas x del norte.
Ejemplos: 
 

Input : 6 4 2 1
        2 3 6 5
Output : Maximum number of bridges = 2
Explanation: Let the north-south x-coordinates
be written in increasing order.

1  2  3  4  5  6
  \  \
   \  \        For the north-south pairs
    \  \       (2, 6) and (1, 5)
     \  \      the bridges can be built.
      \  \     We can consider other pairs also,
       \  \    but then only one bridge can be built 
        \  \   because more than one bridge built will
         \  \  then cross each other.
          \  \
1  2  3  4  5  6 

Input : 8 1 4 3 5 2 6 7 
        1 2 3 4 5 6 7 8
Output : Maximum number of bridges = 5

Enfoque: Es una variación del problema LIS . Los siguientes son los pasos para resolver el problema.
 

1. Ordene los pares norte-sur sobre la base del orden creciente de las coordenadas x del sur.
2. Si dos coordenadas x del sur son iguales, ordene según el orden creciente de las coordenadas x del norte.
3. Ahora encuentre la subsecuencia creciente más larga de las coordenadas x del norte.
4. Una cosa a tener en cuenta es que en la subsecuencia creciente un valor puede ser mayor o igual a su valor anterior.

También podemos ordenar sobre la base de las coordenadas x del norte y encontrar el LIS en las coordenadas x del sur.
 

// C++ implementation of building bridges
#include <bits/stdc++.h>
 
using namespace std;
 
// north-south coordinates
// of each City Pair
struct CityPairs
{
    int north, south;
};
 
// comparison function to sort
// the given set of CityPairs
bool compare(struct CityPairs a, struct CityPairs b)
{
    if (a.south == b.south)
        return a.north < b.north;
    return a.south < b.south;
}
 
// function to find the maximum number
// of bridges that can be built
int maxBridges(struct CityPairs values[], int n)
{
    int lis[n];
    for (int i=0; i<n; i++)
        lis[i] = 1;
         
    sort(values, values+n, compare);
     
    // logic of longest increasing subsequence
    // applied on the northern coordinates
    for (int i=1; i<n; i++)
        for (int j=0; j<i; j++)
            if (values[i].north >= values[j].north
                && lis[i] < 1 + lis[j])
                lis[i] = 1 + lis[j];
         
         
    int max = lis[0];
    for (int i=1; i<n; i++)
        if (max < lis[i])
            max = lis[i];
     
    // required number of bridges
    // that can be built       
    return max;       
}
 
// Driver program to test above
int main()
{
    struct CityPairs values[] = {{6, 2}, {4, 3}, {2, 6}, {1, 5}};
    int n = 4;
    cout << "Maximum number of bridges = "
             << maxBridges(values, n);   
    return 0;
}

// Java Program for maximizing the no. of bridges
// such that none of them cross each other
 
import java.util.*;
 
class CityPairs // Create user-defined class
{
    int north, south;
    CityPairs(int north, int south) // Constructor
    {
        this.north = north;
        this.south = south;
    }
}
// Use Comparator for manual sorting
class MyCmp implements Comparator<CityPairs>
{
    public int compare(CityPairs cp1, CityPairs cp2)
    {
        // If 2 cities have same north coordinates
        // then sort them in increasing order
        // according to south coordinates.
        if (cp1.north == cp2.north)
            return cp1.south - cp2.south;
 
        // Sort in increasing order of
        // north coordinates.
        return cp1.north - cp2.north;
    }
}
public class BuildingBridges {
    // function to find the max. number of bridges
    // that can be built
    public static int maxBridges(CityPairs[] pairs, int n)
    {
        int[] LIS = new int[n];
        // By default single city has LIS = 1.
        Arrays.fill(LIS, 1);
 
        Arrays.sort(pairs, new MyCmp()); // Sorting->
                                         // calling
        // our self made comparator
 
        // Logic for Longest increasing subsequence
        // applied on south coordinates.
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[i].south >= pairs[j].south)
                    LIS[i] = Math.max(LIS[i], LIS[j] + 1);
            }
        }
        int max = LIS[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, LIS[i]);
        }
 
        // Return the max number of bridges that can be
        // built.
        return max;
    }
 
    // Driver Program to test above
    public static void main(String[] args)
    {
        int n = 4;
        CityPairs[] pairs = new CityPairs[n];
        pairs[0] = new CityPairs(6, 2);
        pairs[1] = new CityPairs(4, 3);
        pairs[2] = new CityPairs(2, 6);
        pairs[3] = new CityPairs(1, 5);
        System.out.println("Maximum number of bridges = "
                           + maxBridges(pairs, n));
    }
}

# Python implementation of building bridges
 
# Function to find the maximum number
# of bridges that can be built
def maxBridges(values,n):
    # Sort the elements first based on south values
    # and then based on north if same south values
    values.sort(key=lambda x:(x[0],x[1]))
    # Since southern values are sorted northern values are extracted
    clean = [values[i][1] for i in range(n)]
    # logic of lis applied on northern co-ordinates
    dp = [1 for i in range(n)]
    for i in range(1,len(clean)):
        for j in range(i):
            if clean[i] >= clean[j] and dp[i] < dp[j]+1:
                dp[i] = dp[j]+1
    # required number of bridges that can be built
    return max(dp)
values=[[6,2],[4,3],[2,6],[1,5]]
n=len(values)
print("Maximum number of bridges =", maxBridges(values,n))

Producción: 
 

Maximum number of bridges = 2

Complejidad temporal: O(n ² )

Enfoque – 2 (Optimización en LIS)

Nota: esta es la variación/aplicación de la subsecuencia creciente más larga (LIS).

Paso -1 Inicialmente, deje que un lado esté al norte del puente y el otro lado al sur del puente.

Paso -2 Tomemos el lado norte y ordenemos el elemento con respecto a su posición.

Paso -3 Según el lado norte se ordena, por lo tanto, está aumentando y si aplicamos LIS en el lado sur, podremos obtener los puentes que no se superponen.

Nota: la subsecuencia creciente más larga se puede realizar en O (NlogN) utilizando la ordenación de paciencia.

La optimización principal radica en el hecho de que el elemento más pequeño tiene una mayor probabilidad de contribuir en LIS.

Entrada: 6 4 2 1

          2 3 6 5

Paso 1: ordene la entrada en la posición norte del puente.

1 2 4 6  

5 6 3 2

Paso -2 Aplicar LIS en South Bank que es 5 6 3 2

En la optimización de LIS, si encontramos un elemento que es más pequeño que el elemento actual, reemplazamos, detenemos el flujo actual y comenzamos con el nuevo elemento más pequeño. Si encontramos un elemento más grande que el elemento actual, incrementamos la respuesta.  

5————- >6 (Respuesta =2) HALT encontramos 3 que es menor que 6  

3 (Respuesta = 1) HALT encontramos 2 que es menor que 3

2 (Respuesta=1)

RESPUESTA FINAL = 2

#include<bits/stdc++.h>
using namespace std;
 
int non_overlapping_bridges(vector<pair<int,int>> &temp,int n)
{
    //Step - 1 Sort the north side.
    sort(temp.begin(),temp.end());
    // Create the Dp array to store the flow of non overlapping bridges.
    // ans-->Store the final max number of non-overlapping bridges.
    vector<int> dp(n+1,INT_MAX);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int idx=lower_bound(dp.begin(),dp.end(),temp[i].second)-dp.begin();
        dp[idx]=temp[i].second;
        ans=max(ans,idx+1);
    }
    return ans;
}
 
int main()
{
    int n=4;
    vector<pair<int,int>> temp;
    temp.push_back(make_pair(6,2));
    temp.push_back(make_pair(4,3));
    temp.push_back(make_pair(2,6));
    temp.push_back(make_pair(1,5));
     
    cout<<non_overlapping_bridges(temp,n)<<endl;
    return 0;
}

SALIDA – 2

Complejidad del tiempo – O(NlogN)

Complejidad espacial – O(N)

Referencias de problemas: 
https://www.geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis/
Referencias de soluciones: 
https://www.youtube.com/watch?v=w6tSmS86C4w
Este artículo es una contribución de Ayush Jauhari . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.