algorithm - 跟进: Find the optimal sequence of stops where the number of stops are fixed

Question

我正在尝试编写以下问题的代码:

在 a₀, a₁, ..., a_n 处有 n 个酒店，使得 0 < a ₀ < a₁ < ... < a_n。您唯一可以停留的地方是这些酒店，但您可以选择停靠的酒店。您必须停在最后一家酒店(距离 a_n)，这是您的目的地。此外，您需要在正好 d 天内完成您的旅程(即必须在两者之间进行 d-1 次停留)。如果您在一天内行驶了 x 英里，则当天的费用为 x²。您希望计划您的旅行以最小化总成本 - 即所有旅行天数的每日成本总和。找到最佳的停留酒店顺序。

我想出了这个 dp 解决方案:

让dp(i)是使最后一站是酒店 i 的最低成本。基本案例:dp(0)=0 .

为了计算 dp(i)，我考虑了所有可能的位置 0<=k<i ，我们之前可能已经停下来了。因此，递归关系变为:

for i=1;i<=n;i++
  dp(i)=inf
  prev(i)=undefined
  for k=0;k<i;k++
    if (dp(i)>dp(k)+(ai-ak)^2)
      dp(i) = dp(k)+(ai-ak)^2)
      prev(i) = k 

我们如何确保该算法恰好进行 d 次停顿？

Answer 1

我也在你之前的问题上写了这个答案，但我认为你忽略了它。无论如何，让我知道这种方法是否有用。

您的算法会给您止损点 (int[] k) 的位置，这将在不考虑 d 的情况下将您的成本降至最低。我从你的问题中得知你想将这些 k 站转换为 d 站。

有3种情况:

1)

k.length == d;

问题解决了

2)

k.length < d;

while(k.length!=d) 求所有n的a(n-1)和a(n)之间的最小距离(min)。从第一家酒店开始遍历。查找 a(n) - a(n-1) 为最小值的第一个匹配项。现在，如果这两家酒店在您的 k 中，请找到下一个出现的位置，否则中断您的停靠点以将其作为单独的停靠点包括在 k 中并重复。

如果您到达旅馆的尽头，您可以使用第二个最小距离来执行此操作，依此类推，直到收敛。

3)

k.length > d;

while(k.length!=d) 这次你需要找到 k 中两个邻居之间的最小距离。将两个邻居合并为一站，直到收敛。

我不确定这种方法是最佳方法还是正确方法，但这是我的两分钱。