Building Bridges - Dynamic Programming Solutions

This is a C++ Program that Solves Building Bridges Problem using Dynamic Programming technique.

Problem Description

There is a river. There are n cities on both sides of the river (not necessarily in the same order). Bridges are to be built on the river for every city (from one end of the river to the other end where the same city is located). But no two bridges should intersect. Find out the maximum number of cities for which the bridges can be built over the river.

NOTE- For every city i on one end, there is a city i on the other end.

Problem Solution

This problem is a variant longest increasing subsequence(LIS). First, we reorder the numbering of cities based on ordering of the other end. Now, the answer to the problem is simply the simply the LIS of the cities on the first end. (Look at the example below for further clarification).

Expected Input and Output

Case-1:

 
There are 4 cities.
The cities on first end of the river are in order 4 1 3 2
The cities on other end of the river are in order 1 3 4 2
 
First, we reorder the numbering of cities based on ordering of the other end
first end after reordering 3 1 2 4
other end after reordering 1 2 3 4
 
Now, simply calculate longest increasing subsequence of the cities on first end(after reordering).
 
LIS(3,1,2,4)=3
So, there can be atmost 3 non-intersecting bridges for this example.

Program/Source Code

Here is source code of the C++ Program to Solve Building Bridges Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<utility>
```
```
#include<vector>
```
```
#include<algorithm>
```
```
#include<map>
```
```
 
```
```
using namespace std;
```
```
 
```
```
 
```
```
int lis(int a[], int n)
```
```
{ 
```
```
    int i, j;
```
```
 
```

    //create an array b of size n ie, b[n]

    //b[i] represents the value of longest increasing subsequence with a[i] being the last element

```
 
```

    //b[i]=longest increasing subsequence for the array a[0...i] by including a[i] in the subseuence

```
    //at the end
```
```
 
```
```
    int b[n];
```
```
 
```

    //Since, we are definitely including a[i] for the calculation of b[i], b[i] will

    //either be equal to 1 or greater than 1

```
    //so, initialize b
```
```
    for(i=0;i<n;i++)
```
```
        b[i]=1;
```
```
 
```
```
 
```
```
    //now, we have to fill this b array
```
```
 
```

    //we will calulate the value of b[i] for every 1<=i<=n by checking whether any subsequence

    //b[0], b[1],...,b[i-1] can fit before a[i] and then selecting the maximum out of them

```
    for(i=1;i<n;i++)
```
```
    {
```

        //for every i, we will check all values of 0<=j<i for subsequences b[j] to which a[i]

        //could be appended and select the longest one

```
        for(j=0;j<i;j++)
```
```
        {
```

            //if the current element ie, the ith element has value greater than jth element, that

            //means a[i] can be appended after b[j]

            //Since, we are interested in finding the longest of such subsequences, we will consider

            //only those values of b[j] that are greater than or equal to b[i]

            if(a[i]>a[j] && b[i]<b[j]+1)

```
            {
```
```
                b[i]=b[j]+1;
```
```
            }
```
```
        }
```
```
    }
```
```
 
```

    //now, we have calculated all the values of b[i] for 0<=i<n

    //The length of the longest increasing subsequence of the given array is the maximum of all

    //these values because the longest increasing subsequence can end with any element of the array

```
 
```

    //finding maximum element in b array

```
    int max=0;
```
```
 
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        if(b[i]>max)
```
```
            max=b[i];
```
```
    }
```
```
 
```
```
    return max;
```
```
}
```
```
 
```
```
 
```
```
int main()
```
```
{
```
```
    int i;
```
```
    int n;
```
```
    int index;
```
```
 
```

    cout<<"Enter the total number of cities"<<endl;

```
    cin>>n;
```
```
 
```
```
    int first_end[n];
```
```
    int other_end[n];
```
```
    map<int,int> mp;
```
```
    int reorder_first_end[n];
```
```
 
```

    cout<<"Enter the ordering of cities on first end"<<endl;

```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>first_end[i];
```
```
        mp[first_end[i]]=i;
```
```
    }
```
```
 
```

    cout<<"Enter the ordering of cities on the other end"<<endl;

```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>other_end[i];
```
```
 
```
```
        //reordering
```
```
        index=mp[other_end[i]];
```
```
        reorder_first_end[index]=i+1;
```
```
    }
```
```
 
```

    cout<<"Maximum number of cities for which bridges can be made is "<<endl;

```
    cout<<lis(reorder_first_end,n);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the cities on both the ends. Then we will reorder the number of cities on the first end. We pass these reordered numbering of cities on first end to the function lis as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

Runtime Test Cases

 
Case-1:
$ g++ building_bridges.cpp
$ ./a.out
Enter the total number of cities
4
Enter the ordering of cities on first end
4 1 3 2
Enter the ordering of cities on the other end
1 3 4 2
Maximum number of cities for which bridges can be made is 
3

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Box Stacking Problem using Dynamic Programming

» Next - 0-1 Knapsack Problem using Dynamic Programming

Related Posts:

Check Data Structure Books
Check Computer Science Books
Apply for Computer Science Internship
Check Programming Books
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: