PUERTA | PUERTA-CS-2005 | Pregunta 87

Nos dan 9 tareas T1, T2…. T9. La ejecución de cada tarea requiere una unidad de tiempo. Podemos ejecutar una tarea a la vez. Cada tarea Ti tiene una ganancia Pi y se gana una fecha límite di Ganancia Pi si la tarea se completa antes del final de la unidad de tiempo dith.

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 

¿Se completan todas las tareas en el cronograma que da el máximo beneficio?
(A) Se completaron todas las tareas
(B) T1 y T6 se omitieron
(C) T1 y T8 se omitieron
(D) T4 y T6 se omitieron

Respuesta: (D)
Explicación:

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 

Para maximizar las ganancias, podemos terminar las tareas en el siguiente orden T7, T2, T9, T5, T3, T8, T1
Cuestionario de esta pregunta