带有最小成本的加油站算法？贪心还是动态规划？

Question

我有一个由n个服务站D[]组成的数组，表示每个服务站i距离高速公路起点的距离为D[i]。

我还有一个成本数组C[]，其中C[i]表示在服务站i维修车辆的成本。

我必须在第一个服务站进行车辆维护，我的汽车在两个服务站之间最多可行驶100英里。

如何以最少的成本从高速公路起点到终点获得最有效的算法（需要知道停靠在哪些车站）？我已经找到了一种贪心解决方案来最小化停留次数，但对于成本最少的情况，我正在考虑DP。最优子问题如下：

bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100)

并且有一个单独的数组last[j]，其中包含停靠的最后一个站点，这将是上面子问题中最好的i。

这是否是正确的方法，还是有更好的贪心/动态规划解决方案？

- Anagha

---

我看不出有贪心解法。动态规划的递推公式是正确的。通过使用一个单调队列，你可以在 O(1) 的时间内找到最小值，从而使运行时间为 O(n)，这是最优解，并且具有低常数因子。即使你的自行车行驶范围是不变的，这种方法也可以使用。 - Niklas B.

@NiklasB。实际上他的解决方案是贪心算法，每次停靠时他只会考虑成本最低的选项..他的解决方案运行良好，但并不是最优的，因为他没有考虑每个距离上有多少汽油以及他可以用什么价格重新加满多少汽油，这使得问题更加复杂，并且更便宜的单位气体价格并不总是使停靠成为最佳选择。 - Khaled.K

@KhaledAKhunaifer 请仔细阅读我的问题，我不考虑有多少汽油存在，因为这不是加油站的问题，而是一种变化。这是一个服务站问题，我必须在停留在给定的站点 i 时每次进行固定费用 C[i]。 - Anagha

正如Niklas B.所提到的，您可以从终点站开始向后遍历，每次经过每个站点时，更新到达该站点的最小成本，以便到达终点站。我没有看到任何贪心算法。 - Pham Trung

@Khaled：这是一个示例实现，也许可以帮助说服你：http://ideone.com/gm5eit - Niklas B.

Answer 1

这句话的英译中文是：“这个重复可以更好地写成”。同时，保留了HTML格式且没有进行解释。

bestcost_serviced_at[j] =
  min(0<i<j: bestcost_serviced_at[i] + C[j] s.t. D[j]-D[i] <= 100)

因为循环假设车辆实际停在站点j进行服务时，可以得到最优成本。

因此，该问题的解决方案是

min (j: bestcost_serviced_at[j] s.t. highway_end - D[j] <= 100)

我认为贪心算法不会奏效。

- Antti Huima

Answer 2

我认为你的DP有点不完整，这里是一个更全面的DP递归：

if(highway_end-D[i]>100) {

   minCost[i] = min(0<i<j && D[j]-D[i] <= 100 : minCost[j]+C[i])
} 

else  minCost[i]  = C[i]     

minCost[i] = minimum cost to reach destination if you have filled up at i

根据距离起点的距离对车站进行排序，并在高到低的车站距离中使用DP。使用排序后的数组查找距离不超过100英里的邻近车站。

编辑： -

可以使用最小堆在O（NlogN）时间内完成。

- Vikram Bhat

---

可以在O(n)中实现，但如果距离预先排序，则可以实现。 - Niklas B.

@NiklasB. 即使已经预排序，如何满足每个子问题中的 D[j]-D[i]<=100 和 min(minCost[j]) 的 O(1) 时间复杂度要求？ - Vikram Bhat

线段树每次转换的时间复杂度为O(log n)。正如我之前提到的，使用滑动窗口算法的单调队列甚至可以实现常数时间的转换。稍后我会写出一个答案。 - Niklas B.

如果您感兴趣，可以查看我的回答，其中有一个简单的O(n)算法来解决这个递归问题。 - Niklas B.