Possible way to find the actual billboard locations in the Billboard Highway Problem [Dynamic Progra-CodePudding

I've been learning about dynamic programming the past few days and came across the Highway Billboard Problem. From what I can understand we are able to find the maximum revenue that can be generated from the possible sites, revenue, size of the highway and the minimum distance between two certain billboards. Is there a possible way we can also find out the actual billboard locations alongside the maximum revenue.

For the code I've been looking at this https://www.geeksforgeeks.org/highway-billboard-problem/

CodePudding user response：

Yes, it is possible to write down the sequence of the chosen sites.

There are two max function calls. Replace them by own maximum choice with if, and inside branch where current site is used, add current position to list (to the emptied list in the first max clause, as far as I understand)

For example,

maxRev[i] = max(maxRev[i-1], revenue[nxtbb]);

change to this (pseudocode, did not check validity)

if (revenue[nxtbb] > maxRev[i-1]) {
    maxRev[i] = revenue[nxtbb];
    sitelist.clear();
    sitelist.push(i);
}
else
    maxRev[i] = maxRev[i-1];

and

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

change to

if (maxRev[i-t-1] revenue[nxtbb] > maxRev[i-1]) {
   maxRev[i] = maxRev[i-t-1] revenue[nxtbb];
   sitelist.push(i);
}
 else
    maxRev[i] = maxRev[i-1];