利润最小化，有截止期的作业调度

Question

我面临着问题，在计算给定的5个工作的最低利润与截止日期。

利润为(P1，P2...P5)=(20,15,10,1,6)，截止日期分别为(2,2,1,3,3)。我对这个问题的解决方案是：

+----------+----+-----+---------+
| Deadline | 1  |  2  |    3    |
+----------+--------+-----------+
|    Jobs  | J4 | J5  | (Empty) |
+----------+--------+-----------+

我把最后一个单元格留空了，因为在填完J5和J6之后，在第三个小时内就不能再做其他工作了。根据这个，利润是7。

这是正确的吗？

PS:一个作业需要一个小时，并且一次只能分配一个作业。

Answer 1

如果需要填充所有小时的空位并获得最小利润，则需要进行

我会这样说：

1. 根据(deadline_max，profit_min)对您的作业进行排序：J(4,5,2,1,3) = P(1,6,15,20,10)，D(3,3,2,2,1).
2. Start从最高小时/截止日期开始，即3。只有deadline =3的作业才能放入此小时。
3. Take the first (最低点)= 1 = J4。尽管如此，deadline 3的剩余部分仍然可以用于deadline 3的下一个值，即deadline 6，并将其与deadline 2的第一个值进行比较:如果它较小，则应用此作业，如果不是deadline 2的第一个作业。因为它较小，所以deadline 2的作业为J5.
4. Now，deadline 3&2的作业，并且您希望检查deadline 1。对于deadline #1，可接受的最高截止时间为deadline #1。取最小的那个(这是唯一的作业)。J3.

= 10

那么回答是：J3，J5，J1。总最低利润= 17