Esto es muy similar al problema de programación de intervalos ponderados que se puede resolver con programación dinámica. La variación es que cada trabajo no tiene una hora de inicio y finalización especificada, sino solo una fecha límite en la que el trabajo debe completarse.
Primero, clasifique los trabajos en orden ascendente de fecha límite. Esto define un orden de procesamiento utilizado en el algoritmo de programación dinámica. Ahora podemos crear una tabla donde el elemento [math] i ^ {th} [/ math] es la bonificación máxima alcanzable con los primeros trabajos [math] i [/ math] en la lista.
Comenzamos con el trabajo con la fecha límite más temprana, y la bonificación de este trabajo se almacena como el primer elemento en la tabla. También almacenamos el tiempo de finalización más temprano posible (que, por ejemplo, si comenzamos en t = 0, la duración es de 3 unidades de tiempo y la fecha límite es t = 5, almacenaríamos t = 3 como el tiempo de finalización). Luego tomamos el segundo trabajo y vemos si se puede programar con el primer trabajo (tome la fecha límite de duración del trabajo 2 y verifiquemos si es posterior a la hora de finalización del trabajo 1) y, de ser así, agregamos su bonificación a la del trabajo 1 y guárdelo en la segunda ranura de la mesa. Si no, lo comparamos con la bonificación del trabajo 1 y almacenamos el mayor valor en el segundo espacio.
- ¿Qué significa ejecutar una consulta?
- ¿Cuándo la regresión logística funciona mal y se debe preferir la máquina de vectores de soporte (SVM)?
- Cómo ganar dinero para comprar una MacBook pro
- ¿Puede una biblioteca de aprendizaje automático integrarse con Django? ¿Si es así, cómo?
- Expresiones regulares (informática): ¿Cómo minimizo este DFA?
Ahora generalizamos al paso [math] i ^ {th} [/ math] en el proceso. Primero encontramos la mayor bonificación que podemos lograr en trabajos anteriores. Para hacer esto, una vez más tomamos la fecha límite como la última hora de inicio posible de este trabajo y luego hacemos una búsqueda binaria en los trabajos anteriores para encontrar la última hora de finalización que no entre en conflicto con hacer este trabajo. Al hacer esto, hemos eliminado los trabajos intermedios como posibilidades. Así que ahora tomamos la bonificación de los trabajos realizados anteriormente y la agregamos a la bonificación del trabajo [math] i ^ {th} [/ math] y comparamos esto con la bonificación calculada de los primeros trabajos i-1 (que es fácilmente accedido marcando el elemento anterior en la tabla). Cualquiera que sea mayor, almacenamos este valor de bonificación en la ranura [math] i ^ {th} [/ math] de la tabla, así como el tiempo de finalización correspondiente. Si elegimos el trabajo i, entonces el tiempo de finalización es el de los trabajos previamente seleccionados + la duración del trabajo i, de lo contrario, es solo el tiempo de finalización de los primeros trabajos i-1.
Nota: Debido a que no podemos programar cada trabajo, puede haber una secuencia consecutiva en la tabla que tenga el mismo tiempo de finalización, lo que puede afectar nuestros resultados al realizar la búsqueda binaria. Esto no es un problema porque si todos tienen el mismo tiempo de finalización, eso significa que todos tienen el mismo subconjunto de trabajos elegidos y, por lo tanto, la misma bonificación, por lo que no importa.
Hacemos esto para todos los trabajos y el bono en el elemento [math] n ^ {th} [/ math] en la tabla nos da el bono máximo alcanzable. La complejidad es [matemáticas] O (n \; log \; n) [/ matemáticas] porque ese es el momento de ordenar y también estamos haciendo n pasos en la programación dinámica y cada uno requiere [matemáticas] O (log \; n) [/ math] tiempo para hacer la búsqueda binaria.
