Dynamic Programming - Highway Billboard Problem | Algorithms

Dynamic Programming - Highway Billboard Problem | Algorithms
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)  

    public int maxRevenue(int[] billboard, int[] revenue, int distance, int milesRes) {
        int[] MR = new int[distance + 1];
        //Next billboard which can be used will start from index 0 in billboard[]
        int nextBillBoard = 0;
        //example if milesRes = 5 miles then any 2 bill boards has to be more than
        //5 miles away so actually we can put at 6th mile so we can add one mile milesRes
        milesRes = milesRes + 1; // actual minimum distance can be between 2 billboards
        MR[0] = 0;

        for (int i = 1; i <= distance; i++) {
            //check if all the billboards are not already placed
            if(nextBillBoard < billboard.length){
                //check if we have billboard for that particular mile
                //if not then copy the optimal solution from i-1th mile
                if (billboard[nextBillBoard] != i) {
                    //we do not have billboard for this particular mile
                    MR[i] = MR[i - 1];
                } else {
                    //we do  have billboard for this particular mile
                    //now we have 2 options, either place the billboard or ignore it
                    //we will choose the optimal solution
                    if(i>=milesRes){
                        MR[i] = Math.max(MR[i - milesRes] + revenue[nextBillBoard], MR[i - 1]);
                    }else{
                        //there are no billboard placed prior to ith mile
                        //we will just place the billboard
                        MR[i] = revenue[nextBillBoard];
                    }

                    nextBillBoard++;
                }
            }else{
                //All the billboards are already placed
                //for rest of the distance copy the previous optimal solution
                MR[i] = MR[i - 1];
            }

        }

        //System.out.println(Arrays.toString(MR));
        return MR[distance];
    }

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.

http://www.geeksforgeeks.org/highway-billboard-problem/

Let maxRev[i], 1 <= i <= M, be the maximum revenue generated from beginning to i miles on the highway. Now for each mile on the highway, we need to check whether this mile has the option for any billboard, if not then the maximum revenue generated till that mile would be same as maximum revenue generated till one mile before. But if that mile has the option for billboard then we have 2 options:
1. Either we will place the billboard, ignore the billboard in previous t miles, and add the revenue of the billboard placed.
2. Ignore this billboard. So maxRev[i] = max(maxRev[i-t-1] + revenue[i], maxRev[i-1])

Time Complexity: O(M), where M is distance of total Highway.
Auxiliary Space: O(M).

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];

}

Read full article from Dynamic Programming - Highway Billboard Problem | Algorithms