Q:

Consider a highway of M miles. The task is to place billboards on the highway such that revenue is maximized

mahmoud2506
Save to bookmark
|
2022-05-01
|
  270 
0

Highway billboard

Consider a highway of M miles. The task is to place billboards on the highway such that revenue is maximized. The possible sites for billboards are given by number x1 < x2 < ... < x(n-1) < xn specifying positions in miles measured from one end of the road. If we place a billboard at position xi, we receive a revenue of ri > 0. The constraint is that no two billboards can be placed within t miles or less than it.

    Input:
    M=15, n=5
    x[n]= {6,8,12,14,15}
    revenue[n] = {3,6,5,3,5}
    t = 5

    Output:
    11

Explanation with example

So, we have to maximize the revenue by placing the billboards where the gap between any two billboard is t.

Here,

The corresponding distances of the billboards with respect to the origin are,

    x[5]= {6,8,12,14,15}

We can augment the origin, so the augmented array becomes: (no need to augment if origin revenue exists)


    x[6]= {0,6,8,12,14,15}
    t=5

The graphical interpretation of the billboards is like following:

Highway billboard

Figure 1: Billboards

The augmented revenue array:

    revenue[6] = {0,3,6,5,3,5}

Now, the brute force approach can be to check all the possible combination of billboards and updating the maximum revenue accumulated from each possible combinations.

Few of such possible combinations can be:

Highway billboard

So, maximum revenue that can be collected is 11.

For any billboard bi we have three choices

  1. Don't pick bi
  2. Start from bi
  3. Pick bi and other billboards accordingly

Say,

    M(i)=maximum revenue upto first i billboards

So,

    M(0)=0
    if bi is not picked, M(i)=M(i-1)
    if billboard placement starts from bi M(i)=r[i]
    If we place bi then need to pace bj where d[i]>d[j]-t such that revenue maximizes
    
    So,
    Highway billboard
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

We convert the above recursion to dynamic programing as there will many overlapping sub problems solving the recursion. (Try to generate the recursion tree yourself)

    1) Construct DP[n] for n billboards
        // considering billboard placing starts from it
    2) Fill the array with base value which is r[i] 

    3) for  i=1 to n-1
            // recursion case 1 and 2
            // either not picking ith billboard or starting 
            // from ith billboard which ever is maximum
            dp[i] = max(dp[i-1],dp[i]);
            // recursion case 3
            // picking ith billboard
            for j=0 to i-1
            if(a[j]< a[i]-k)//feasible placing
                dp[i]= max(dp[i],dp[j]+r[i]);
            end for
        end for
        Result is dp[n-1]

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

int max(int x, int y)
{
    return (x > y) ? x : y;
}

int billboard(vector<int> a, vector<int> r, int n, int k)
{
    int dp[n];

    for (int i = 0; i < n; i++)
        dp[i] = r[i];

    //base value
    dp[0] = r[0];
    for (int i = 1; i < n; i++) {
        //first two recursion case
        int mxn = max(dp[i - 1], dp[i]);
        //picking ith billboard, third recursion case
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] - k)
                mxn = max(mxn, dp[j] + r[i]);
        }
        dp[i] = mxn;
    }

    return dp[n - 1];
}

int main()
{
    int n, k, item, m;

    cout << "Enter highway length:\n";
    cin >> m;
    cout << "Enter number of billboards\n";
    cin >> n;
    cout << "Enter minimum distance between any two billboards\n";
    cin >> k;

    vector<int> a;
    vector<int> r;

    cout << "Enter billboard distances one by one from origin\n";
    for (int i = 0; i < n; i++) {
        cin >> item;
        a.push_back(item);
    }
    cout << "Enter revenues for the respective billboards\n";
    for (int i = 0; i < n; i++) {
        cin >> item;
        r.push_back(item);
    }

    if (a[0] == 0) {
        a.insert(a.begin(), 0);
        r.insert(r.begin(), 0);
        n = n + 1;
    }

    cout << "Maximum revenue that can be collected is: " << billboard(a, r, n, k) << endl;

    return 0;
}

Output

RUN 1:
Enter highway length:
20
Enter number of billboards
5
Enter minimum distance between any two billboards
5
Enter billboard distances one by one from origin
3 7 12 13 14
Enter revenues for the respective billboards
15 10 1 6 2
Maximum revenue that can be collected is: 21

RUN 2:
Enter highway length:
15
Enter number of billboards
5
Enter minimum distance between any two billboards
5
Enter billboard distances one by one from origin
6 8 12 14 15
Enter revenues for the respective billboards
3 6 5 3 5
Maximum revenue that can be collected is: 11

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Top C++ Dynamic programming problems for interviews
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given two strings string1 and string2 find the min... >>
<< How many non-decreasing numbers can be generated o...