java - 最小化利润，工作安排与最后期限

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 之后，第 3 个小时就没有其他工作可以完成了。据此，利润为 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. 从最高时间/截止日期开始，即 3。只有 deadline = 3 的作业才能适合这个小时。
3. 取第一个(最低的)= 1 = J4。截止日期 3 的剩余时间仍可用于更短的截止日期。
4. 取 deadline 3 的下一个值 6 并将它与 deadline 2 的第一个值进行比较:如果它小于则应用此作业，如果不是则取 deadline 2 的第一个作业。因为它小于截止日期 2 的作业是 J5。
5. 现在，截止日期 3 和 2 的作业已被占用，您想要检查截止日期 1。小时 #1 可接受的最高截止日期是截止日期 #1。取最小的(这是唯一的工作)。 10 = J3。

那么答案是:J3, J5, J1。总最小利润 = 17