具有三个参数的作业排序问题

Question

我有三个参数的作业排序问题，其中每个任务都有时间要完成（以周为单位），并且必须在其之前完成最后期限。

换句话说，任何一周最多都可以处理Job。所有工作都有严格的期限，这意味着必须在期限之前完成。任务是安排工作，以便积累高利润。

示例

输入：

JobID   Time    Profit    Deadline
  1      8        100        13
  2      1        100        1
  3      1        100        3  
  4      1        100        2
  5      4        100        6

输出

总利润： 400

工作顺序： 2 4 3 1

我一直在尝试应用贪心算法，但它仅适用于两个参数（利润和最后期限），但在这里我必须考虑时间”

Answer 1

该解决方案可以通过动态编程获得。在深入递归之前，需要先发展一些直觉：

（我假设每个任务将在截止日期的最早日期开始。也就是说，在您的示例中，该日期为第1天。）>] >>

Let D_i表示完成任务（或工作）T_i所需的时间（天）。将任务T_i的利润表示为P_i s。

在日历日C（假设日历从截止日期的最早日期开始），您只能根据问题定义执行任务。它可以是T_1，T_2，T_3，T_4或T_5之一。

[如果您在T_1天执行任务C，则意味着您在日历的C - D_1天启动了任务。同样，如果您在T_2天执行任务C，那么您是在几天前开始执行C - D_2任务的，依此类推。

您可能在T_1日执行T_2，T_3，T_4，T_5或C中的任何一项。因此，通过在C天执行序列中的最后一项任务获得的利润是P_1，P_2，P_3，P_4或P_5中的一个。如果将您在最后一天执行的任务T_i的利润加到每个C - D_i的直到1<= i <= 5天的最大利润，您将获得一组可能在C天获得的最大利润]。这些利润中最高的就是您要寻找的东西。最后，答案将是第13

天的解决方案。 （C = 13）

我将由您自己决定如何将其编码为编程结构。从广义上讲，您需要两个变量来进行动态编程递归：

1. 任务集（即建模T_i）
2. 日历天（即建模C）