Weighted Interval Scheduling Dynamic Programming

El Problema de Planificación de Intervalos Ponderados (Weighted Interval Scheduling) es un problema de optimización. Se tienen varios intervalos de tiempo, cada uno con un peso o valor asociado. El objetivo es encontrar un conjunto de intervalos que no se superpongan y que maximicen la suma de sus pesos.

¿Por qué es importante? Este problema modela situaciones reales. Por ejemplo, imagina que cada intervalo es un proyecto con un beneficio económico. El objetivo es seleccionar los proyectos que maximicen el beneficio total, sabiendo que algunos proyectos no se pueden realizar al mismo tiempo porque utilizan los mismos recursos.

La Programación Dinámica es una técnica poderosa para resolver este problema. La idea clave es construir una solución óptima de forma incremental, resolviendo subproblemas más pequeños y combinando sus soluciones.

Pasos para resolverlo con Programación Dinámica:

1. Ordenar los intervalos: Ordena los intervalos por su tiempo de finalización de forma ascendente. Esto simplifica la búsqueda de intervalos compatibles.
2. Definir la subestructura óptima: Sea OPT(j) el valor óptimo (máxima suma de pesos) para los primeros j intervalos.
3. Definir la recurrencia: Para cada intervalo j, tienes dos opciones:
   • Incluir el intervalo j: Si lo incluyes, no puedes incluir los intervalos que se superponen con j. Necesitas encontrar el intervalo p(j) que termina antes de que empiece j y que es el más cercano a j (el "predecesor" compatible de j). En este caso, el valor sería el peso de j más OPT(p(j)).
   • No incluir el intervalo j: En este caso, el valor sería simplemente OPT(j-1).
   Por lo tanto, la recurrencia es: OPT(j) = max(v_j + OPT(p(j)), OPT(j-1)), donde v_j es el peso del intervalo j.
4. Caso base: OPT(0) = 0 (si no hay intervalos, el valor óptimo es 0).
5. Calcular los valores OPT de forma iterativa: Calcula OPT(1), OPT(2), ..., OPT(n) utilizando la recurrencia. Guarda estos valores en una tabla.
6. La solución final: OPT(n) será el valor óptimo para todos los intervalos.
7. Reconstruir la solución: Para encontrar los intervalos que forman la solución óptima, puedes recorrer la tabla OPT y seguir las decisiones que maximizaron el valor en cada paso.

Ejemplo: Imagina tres intervalos: A (1, 3, peso=5), B (2, 5, peso=6), C (6, 7, peso=4). Ordenándolos no cambian el orden ya que ya estan ordenados por tiempo de finalización. p(A)=0, p(B)=0, p(C)=0. Calculando OPT: OPT(0)=0, OPT(1)=max(5+0, 0)=5, OPT(2)=max(6+0, 5)=6, OPT(3)=max(4+0, 6)=6. La solución óptima es el intervalo B con un peso de 6.

La Programación Dinámica convierte un problema complejo en una serie de decisiones sencillas. Almacenar las soluciones a los subproblemas evita recalcular lo mismo una y otra vez, haciendo que el algoritmo sea eficiente.