Dynamic Programming – Highway Billboard Problem

Objective:  Suppose you’re managing construction of billboards on the Rocky & Bullwinkle Memorial Highway, a heavily traveled stretch of road that runs west-east for M miles. The possible sites for billboards are given by numbers x1 < x2 < · · · < xn, each in the interval [0, M], specifying their position in miles measured from the western end of the road. If you place a billboard at position xi , you receive a revenue of ri > 0.

Regulations imposed by the Highway Department require that no two billboards be within five miles or less of each other. You’d like to place billboards at a subset of the sites so as to maximize your total revenue, subject to this restriction.

Problem Source: https://cgi.csc.liv.ac.uk/~martin/teaching/comp202/Exercises/Dynamic-programming-exercises-solution.pdf

Example:

int[] x = {6, 7, 12, 13, 14};
int[] revenue = {5, 6, 5, 3, 1};
int distance = 20;
int milesRestriction = 5;

Output: Maximum revenue can be generated :10 ( x1 and x3 billboard will be placed)

Approach:

We will solve this problem using dynamic programming in bottom-up manner.

let’s say

"MR(i)  is Maximum Revenue generated for i miles in highway"

Now for each mile in highway, we need to check whether this mile has option for any billboard, if not then maximum revenue generated till that mile would be same as maximum revenue generated till one mile before.

But if that mile has option for billboard then we have 2 options

  • Either we will place the billboard (ignore the billboards in previous 5 miles) and add the revenue of billboard placed.
  • OR we will ignore the billboard

So we will choose the option which will generate the maximum revenue.

MR(i) = Max{MR(i-6) + Revenue[i], MR[i-1]}

Note: Two bill boards has to be more than 5 miles away so actually we add MR(i-6) with revenue

Highway Billboard Problem

Read the code for more understanding.

Complete Code:

Output:

[0, 0, 0, 0, 0, 0, 5, 6, 6, 6, 6, 6, 10, 10, 10, 10, 10, 10, 10, 10, 10]
Maximum revenue can be generated :10

Track the actual solution: To track the actual solution use MR[]. Start traversing from the end towards start. Whenever value changes means billboard has been place at the location. Note the billboard and jump 5 miles back (no two billboards be within five miles or less of each other) and again traverse backwards and so on.

Track Result - Highway Billboard Problem

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • Oddo Zhang

    When i < milesRes, should not MR[i] = max(revenue[0],….revenue[i])? we can only build one in this range and we should build the most profitable one instead of the one at site i

  • dheeraj singhal

    int[] x = { 6, 7, 13, 14, 21, 28, 29 };
    int[] revenue = { 5, 16, 5, 8, 1, 100, 2 };
    int dyn[] = new int[x.length];
    dyn[0] = revenue[0];
    for (int i = 1; i < x.length; i++) {
    int j;
    int maxRevenue = 0;
    for (j = 0; j 5) {
    if (maxRevenue < dyn[j]) {
    maxRevenue = dyn[j];
    }
    }
    }
    dyn[i] = maxRevenue + revenue[i];

    Then find max from dyn array.

%d bloggers like this: