python - 动态规划递归求解

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

但这并不奏效。

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.