Highway Billboard Problem: Dynamic Programming

In this post we will understand the problem of Highway Billboard Problem and then we will implement the solution using Dynamic Programming.

Problem:

Let’s suppose we got a job to place billboards (advertising hoarding) on a National Highway of length M miles. The possible site for billboards are given by numbers x1 < x2 < ….. < xn-1 < xn, each in the interval [O, M] (M is length of highway), specifying their position in miles measured from one end of the road. If you place a billboard at position xi , you receive a revenue of ri > 0.

There is a restriction that no two billboards can be placed within t miles or less than it.

Examples:

Input : M = 15
        x[] = {6, 9, 12, 14}
        revenue[] = {5, 6, 3, 7}
        t = 2
Output : 18  (Maximum revenue can be generated)

Input : M = 20
        x[]  = {6, 7, 12, 13, 14}
        revenue[] = {5, 6, 5,  3,  1}
        t = 5
Output: 10
By placing two billboards at 6 miles and 12 miles will produce the maximum revenue of 10.

Solution:

Let’s solve this problem using Dynamic Programming approach.

Say maxRev[i], 1 <= i <= M, be the maximum revenue generated from beginning to i miles on the 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 t miles) and add the revenue of billboard placed.
  • OR we will ignore the billboard.

So maximum revenue will be generated by:

maxRev[i] = max(maxRev[i-t-1] + revenue[i], maxRev[i-1])

Now let’s implement this solution in programming:

Solution of Highway Billboard Problem in C++:

Solution of Highway Billboard Problem in Java:

Solution of Highway Billboard Problem in Python:

Source :
https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture18/Lecture18.pdf

Comment to discuss, provide suggestion regarding the problem.