Dynamic Programming — Highway Billboard Problem

Objec­tive:  Sup­pose you’re man­ag­ing con­struc­tion of bill­boards on the Rocky & Bull­win­kle Memo­r­ial High­way, a heav­ily trav­eled stretch of road that runs west-east for M miles. The pos­si­ble sites for bill­boards are given by num­bers x1 < x2 < · · · < xn, each in the inter­val [0, M], spec­i­fy­ing their posi­tion in miles mea­sured from the west­ern end of the road. If you place a bill­board at posi­tion xi , you receive a rev­enue of ri > 0.

Reg­u­la­tions imposed by the High­way Depart­ment require that no two bill­boards be within five miles or less of each other. You’d like to place bill­boards at a sub­set of the sites so as to max­i­mize your total rev­enue, sub­ject to this restriction.

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

Exam­ple:

```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 prob­lem using dynamic pro­gram­ming in bottom-up manner.

let’s say

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

Now for each mile in high­way, we need to check whether this mile has option for any bill­board, if not then max­i­mum rev­enue gen­er­ated till that mile would be same as max­i­mum rev­enue gen­er­ated till one mile before.

But if that mile has option for bill­board then we have 2 options

• Either we will place the bill­board (ignore the bill­boards in pre­vi­ous 5 miles) and add the rev­enue of bill­board placed.
• OR we will ignore the billboard

So we will choose the option which will gen­er­ate the max­i­mum 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 actu­ally we add MR(i-6) with revenue

Read the code for more understanding.

Com­plete Code:

Out­put:

```[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 solu­tion: To track the actual solu­tion use MR[]. Start tra­vers­ing from the end towards start. When­ever value changes means bill­board has been place at the loca­tion. Note the bill­board and jump 5 miles back (no two bill­boards be within five miles or less of each other) and again tra­verse back­wards and so on.

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 prof­itable one instead of the one at site i

• dheeraj sing­hal

int[] x = { 6, 7, 13, 14, 21, 28, 29 };
int[] rev­enue = { 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 maxRev­enue = 0;
for (j = 0; j 5) {
if (maxRev­enue < dyn[j]) {
maxRev­enue = dyn[j];
}
}
}
dyn[i] = maxRev­enue + revenue[i];

Then find max from dyn array.