问题是我有经典的加权间隔调度问题，但有一个额外的要求。这个要求是，从给定的工作中，必须完成一些工作。
我已经用蛮力解决了它。但我需要更有效的解决方案。我用动态规划解决了经典的加权调度问题。但是有了这个约束，我不能。你有什么建议吗。谢谢指教。
问问题
685 次
2 回答
0
好吧，我看不出这个问题与经典的加权间隔调度有什么不同。如果“必须完成”的工作不重叠（如果它们是，那么你有一个定义不明确的问题 - 如何在两个重叠的“必须完成”的工作之间进行选择？），那么你只需要一种方法来使它们的相对权重站立其余的工作。
您可以在 O(n) 中遍历您的作业，并找到最大权重。然后对于“必须完成”的工作，您需要将最大值添加到他们的权重中。这将确保他们将被选中而不是任何其他工作，因为他们的相对权重肯定会高于非优先工作。
正如我所说，唯一的问题是“必须完成”的工作何时重叠。在这种情况下，您将以一些未选择的必须工作结束（因为您必须选择一个必须工作而不是另一个）。
于 2013-11-16T09:01:21.633 回答
0
只需在经典调度问题的基础上再增加一个维度
该维度给出了迄今为止已完成的工作数量
例如。
f[i][j] 表示在时间 i，完成了 j 个工作，最大利润是多少
f[i][j] 可以决定 f[job_end_time[k]][j+1] 给定 job_start_time[k]>=i
于 2013-01-11T08:50:36.660 回答