大门|大门-CS-2005 |问题88

我们有9个任务T1，T2…。T9。每个任务的执行都需要一个时间单位。我们可以一次执行一项任务。每个任务Ti都有一个利润Pi，如果任务在第i个时间单位结束之前完成，则获得最后期限di利润Pi。

Task     T1  T2     T3  T4  T5  T6     T7 T8  T9
Profit   15  20     30  18  18  10     23 16  25
Deadline 7   2      5   3      4   5      2  7   3 

最大利润是多少？ （A） 147 （B） 165 （C） 167 （D） 175 答复: （A） 说明：

Task     T1  T2     T3  T4  T5  T6     T7 T8  T9
Profit   15  20     30  18  18  10     23 16  25
Deadline 7   2      5   3      4   5      2  7   3 

为了实现利润最大化，我们可以按照以下顺序完成任务：T7、T2、T9、T5、T3、T8、T1。

我们得到的最大利润为23+20+25+18+30+16+15=147 这个问题的小测验