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

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

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

Possible way to find the actual billboard locations in the Billboard Highway Problem [Dynamic Programming]

c++

math

dynamic