Tema 2
Algoritmos Greedy
Patrón de examen
Prueba greedy cuando el problema pida maximizar/minimizar y puedas ordenar por algún criterio. Verifica con casos de prueba pequeños.
Explicación
¿Qué es Greedy?
Tomar siempre la decisión localmente óptima esperando que lleve a una solución globalmente óptima.
No siempre funciona, pero cuando funciona es muy eficiente. Requiere demostrar que la elección greedy no descarta la solución óptima.
Ejemplos clásicos
Selección de actividades (Interval Scheduling)
Dado un conjunto de actividades con inicio y fin, seleccionar el máximo número de actividades no solapadas.
Greedy: ordenar por tiempo de finalización, seleccionar siempre la que termina más pronto.
Problema de la moneda
Dar cambio con el mínimo de monedas. Solo funciona con denominaciones específicas (ej: 1, 5, 10, 25). No funciona en el caso general.
Mochila fraccionaria
A diferencia de la mochila 0/1, aquí podemos tomar fracciones. Greedy: ordenar por valor/peso y tomar lo más valioso primero.
Señales de que un problema es Greedy
- Pide maximizar/minimizar algo
- Se puede ordenar por algún criterio obvio
- La elección local no "arruina" opciones futuras