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++:
// C++ program to find maximum revenue by placing
// billboard on the highway with given constraints.
#include<bits/stdc++.h>
using namespace std;
int maxRevenue(int m, int x[], int revenue[], int n, int t)
{
// Array to store maximum revenue at each miles.
int maxRev[m+1];
memset(maxRev, 0, sizeof(maxRev));
// actual minimum distance between 2 billboards.
int nxtbb = 0;
for (int i = 1; i <= m; i++)
{
// check if all billboards are already placed.
if (nxtbb < n)
{
// check if we have billboard for that particular
// mile. If not, copy the previous maximum revenue.
if (x[nxtbb] != i)
maxRev[i] = maxRev[i-1];
// we do have billboard for this mile.
else
{
// We have 2 options, we either take current
// or we ignore current billboard.
// If current position is less than or equal to
// t, then we can have only one billboard.
if (i <= t)
maxRev[i] = max(maxRev[i-1], revenue[nxtbb]);
// Else we may have to remove previously placed billboard
else
maxRev[i] = max(maxRev[i-t-1]+revenue[nxtbb],maxRev[i-1]);
nxtbb++;
}
}
else
maxRev[i] = maxRev[i - 1];
}
return maxRev[m];
}
int main()
{
int m = 20;
int x[] = {6, 7, 12, 13, 14};
int revenue[] = {5, 6, 5, 3, 1};
int n = sizeof(x)/sizeof(x[0]);
int t = 5;
cout << maxRevenue(m, x, revenue, n, t) << endl;
return 0;
}
Output:
10
Solution of Highway Billboard Problem in Java:
class GFG
{
static int maxRevenue(int m, int[] x, int[] revenue, int n, int t)
{
// Array to store maximum revenue at each miles.
int[] maxRev = new int[m + 1];
for(int i = 0; i < m + 1; i++)
maxRev[i] = 0;
// actual minimum distance between 2 billboards.
int nxtbb = 0;
for (int i = 1; i <= m; i++)
{
// check if all billboards are already placed.
if (nxtbb < n)
{
// check if we have billboard for
// that particular mile. If not,
// copy the previous maximum revenue.
if (x[nxtbb] != i)
maxRev[i] = maxRev[i - 1];
// we do have billboard for this mile.
else
{
// We have 2 options, we either take
// current or we ignore current billboard.
// If current position is less than or equal to t,
// then we can have only one billboard.
if (i <= t)
maxRev[i] = Math.max(maxRev[i - 1], revenue[nxtbb]);
// Else we may have to remove previously placed billboard
else
maxRev[i] = Math.max(maxRev[i - t - 1] +
revenue[nxtbb],
maxRev[i - 1]);
nxtbb++;
}
}
else
maxRev[i] = maxRev[i - 1];
}
return maxRev[m];
}
public static void main(String []args)
{
int m = 20;
int[] x = new int[]{6, 7, 12, 13, 14};
int[] revenue = new int[]{5, 6, 5, 3, 1};
int n = x.length;
int t = 5;
System.out.println(maxRevenue(m, x, revenue, n, t));
}
}
// This code is contributed by Ita_c.
Output:
10
Solution of Highway Billboard Problem in Python:
# Python3 program to find maximum revenue
# by placing billboard on the highway with
# given constarints.
def maxRevenue(m, x, revenue, n, t) :
# Array to store maximum revenue at each miles.
maxRev = [0] * (m + 1)
# actual minimum distance between 2 billboards.
nxtbb = 0;
for i in range(1, m + 1) :
# check if all billboards are already placed.
if (nxtbb < n) :
# check if we have billboard for
# that particular mile. If not,
# copy the previous maximum revenue.
if (x[nxtbb] != i) :
maxRev[i] = maxRev[i - 1]
# we do have billboard for this mile.
else :
# We have 2 options, we either take
# current or we ignore current billboard.
# If current position is less than or
# equal to t, then we can have only
# one billboard.
if (i <= t) :
maxRev[i] = max(maxRev[i - 1], revenue[nxtbb])
# Else we may have to remove
# previously placed billboard
else :
maxRev[i] = max(maxRev[i - t - 1] + revenue[nxtbb],maxRev[i - 1]);
nxtbb += 1
else :
maxRev[i] = maxRev[i - 1]
return maxRev[m]
if __name__ == "__main__" :
m = 20
x = [6, 7, 12, 13, 14]
revenue = [5, 6, 5, 3, 1]
n = len(x)
t = 5
print(maxRevenue(m, x, revenue, n, t))
Output:
10
Source :
https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture18/Lecture18.pdf
Comment to discuss, provide suggestion regarding the problem.