动态规划递推公式转化为解决方案

Question

我正在尝试解决加权区间调度问题。基本上，我想出了以下递归公式来获得最优解的长度：

optimum[i] = max(duration(intervals[i]) + opt[prior[i]], opt[i - 1])

prior[i] = 在当前区间开始之前完成的最新的不重叠的计划。

这个递归方法很好用，我得到了正确的解决方案。然而，我想得到实际的时间表，而不仅仅是长度。我该怎么做呢？我尝试从最大的p[i]值开始，并跟随指针直到我到达None / -1 / Null，但这并不总是有效。我认为我需要在解决上述递归问题时跟踪哪些区间需要保留，哪些需要丢弃。我尝试通过以下方式实现：

if (duration(intervals[i]) + optimum[prior[i]] >= optimum[i - 1]) {
  optimum[i] = duration(intervals[i]) + optimum[p[i]];
  retain[i] = true;
}
else {
  optimum[i] = optimum[i - 1];
  retain[i] = false;
  retain[i - 1] = true;
}

但是这样做效果不好。

- Penny Mahar

Answer 1

你可以使用prior[i]和optimum[i]来构建路径。具体来说，你从最优解的i开始。然后路径可以按照以下方式获得。

queue<int> path;
int st = i;
while (st > 0) {
  if (op[st] == op[st-1]) st = st -1;
  else {
    path.push(st);
    st = prior[st];
  }
}
pop each item from queue<int> path, you get the intervals you selected.  

- notbad

---

请注意边界索引。例如，索引从1或0开始，prior[0]应为-1等等。此外，您应确保prior [i]严格小于i。 - notbad

@PennyMahar 是的，应该是 st = prior[st]。我会更新它。可以吗？ - notbad

谢谢！现在循环正常工作，并且除了最高OPT值被两个或多个时隙共享的情况外，它还能给出正确的答案。如果发生这种情况，为什么我们只会选择较低的时隙？如果当前时隙的持续时间大于上一个时隙，那该怎么办？ - Penny Mahar

所以你的意思是应该是 for j in range(len(intervals) + 1): 吗？但这仍然不起作用。 :/ - Penny Mahar

啊，现在可以了。非常感谢你！谢谢！ :) - Penny Mahar