python – 动态编程重现到解决方案

概述我正在尝试解决加权区间调度问题.基本上,我想出了以下重复以获得最佳解决方案的长度： optimum[i] = max(duration(intervals[i]) + opt[prior[i]], opt[i - 1]) 其中prior [i] =在当前间隔开始之前完成的最新非重叠计划. 复发效果很好,我得到了正确的解决方案.但是,我想得到实际的时间表,而不仅仅是长度.我怎样才能做到这一点？我尝试 我正在尝试解决加权区间调度问题.基本上,我想出了以下重复以获得最佳解决方案的长度：

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

其中prior [i] =在当前间隔开始之前完成的最新非重叠计划.

复发效果很好,我得到了正确的解决方案.但是,我想得到实际的时间表,而不仅仅是长度.我怎样才能做到这一点？我尝试从最大的p [i]值开始并跟随指针,直到我达到无/ -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;}

但这并没有奏效.

解决方法 您可以使用prevIoUs [i]以及optimal [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.

总结

以上是内存溢出为你收集整理的python – 动态编程重现到解决方案全部内容，希望文章能够帮你解决python – 动态编程重现到解决方案所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。