在广告牌高速公路问题[动态规划]中找到广告牌实际位置的可能方法

Question

过去几天我一直在学习动态规划，并遇到了公路广告牌问题。根据我的理解，我们能够从可能的地点、收入、高速公路的大小和两个特定广告牌之间的最小距离中找到最大的收入。有没有可能的方法，我们也可以找到实际的广告牌位置，除了最大的收入。

对于代码我一直在看这个https://www.geeksforgeeks.org/highway-billboard-problem/

Answer 1

是的，可以写下所选站点的顺序。

有两个max函数调用。用if替换它们，并在使用当前站点的分支内，将当前位置添加到列表(到第一个max子句中的空列表，据我所知)

例如,

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

更改为此(伪代码，未检查有效性)

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

和

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

改变

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