Problema de selección de actividades

Dejar${\displaystyle S=\{1,2,\ldots ,n\}}$Sea el conjunto de actividades ordenadas por tiempo de finalización. Suponga que${\displaystyle A\subseteq S}$es una solución óptima, también ordenada por tiempo de finalización; y que el índice de la primera actividad en A es${\displaystyle k\neq 1}$, es decir, esta solución óptima no comienza con la elección voraz. Demostraremos que${\displaystyle B=(A\setminus \{k\})\cup \{1\}}$, que comienza con la elección codiciosa (actividad 1), es otra solución óptima. Dado que${\displaystyle f_{1}\leq f_{k}}$y las actividades en A son disjuntas por definición, las actividades en B también son disjuntas. Dado que B tiene el mismo número de actividades que A , es decir,${\displaystyle |A|=|B|}$, B también es óptimo.

Una vez realizada la elección voraz, el problema se reduce a encontrar una solución óptima para el subproblema. Si A es una solución óptima para el problema original S que contiene la elección voraz, entonces${\displaystyle A^{\prime }=A\setminus \{1\}}$es una solución óptima al problema de selección de actividades${\displaystyle S'=\{i\in S:s_{i}\geq f_{1}\}}$.

¿Por qué? Si no fuera así, elijamos una solución B ′ a S ′ con más actividades que A ′ que contenga la opción voraz para S ′. Entonces, al sumar 1 a B ′ se obtendría una solución factible B a S con más actividades que A , lo que contradice la optimalidad.

La versión generalizada del problema de selección de actividades implica seleccionar un conjunto óptimo de actividades no superpuestas de manera que se maximice el peso total. A diferencia de la versión sin ponderación, no existe una solución voraz para el problema de selección de actividades ponderadas. Sin embargo, se puede formular fácilmente una solución de programación dinámica utilizando el siguiente enfoque: ^{[ 1 ]}

Consideremos una solución óptima que contiene la actividad k . Ahora tenemos actividades que no se superponen a la izquierda y a la derecha de k . Podemos encontrar recursivamente soluciones para estos dos conjuntos debido a la subestructura óptima. Como no conocemos k , podemos probar cada una de las actividades. Este enfoque conduce a una${\displaystyle O(n^{3})}$solución. Esto se puede optimizar aún más considerando que para cada conjunto de actividades en${\displaystyle (i,j)}$, podemos encontrar la solución óptima si hubiéramos conocido la solución para${\displaystyle (i,t)}$donde t es el último intervalo no superpuesto con j en${\displaystyle (i,j)}$Esto produce un${\displaystyle O(n^{2})}$solución. Esto se puede optimizar aún más considerando que no necesitamos considerar todos los rangos.${\displaystyle (i,j)}$pero en cambio solo${\displaystyle (1,j)}$. El siguiente algoritmo produce, por lo tanto, un${\displaystyle O(n\log n)}$solución:

Selección ponderada de actividades ( S ) : // S = lista de actividadesordenar S por tiempo de finalizaciónopt [ 0 ] = 0 // opt[j] representa la solución óptima (suma de los pesos de las actividades seleccionadas) para S[1,2..,j]para i = 1 a n :t = búsqueda binaria para encontrar la actividad con tiempo de finalización <= tiempo de inicio para i// Si hay más de una actividad de este tipo, elige la que tenga la última hora de finalización.opt [ i ] = MAX ( opt [ i -1 ], opt [ t ] + w ( i ))devolver opt [ n ]