Los algoritmos greedy (o voraces) son una clase de algoritmos que construyen una solución paso a paso, eligiendo en cada paso la opción que parece ser la mejor en ese momento. Estos algoritmos son simples y eficientes, pero no siempre garantizan la solución óptima para todos los problemas.

1. Selección Greedy: En cada paso, se elige la opción que parece ser la mejor en ese momento.
2. Solución Parcial: La solución se construye paso a paso, añadiendo elementos a una solución parcial.
3. Irrevocabilidad: Una vez que se toma una decisión, no se puede deshacer.
4. Optimalidad Local: Cada paso se toma con la esperanza de que la solución localmente óptima conduzca a una solución globalmente óptima.

1. Problema del Cambio de Monedas: Dado un conjunto de denominaciones de monedas y una cantidad total, encontrar la mínima cantidad de monedas que sumen esa cantidad.
2. Problema del Viajante de Comercio (versión aproximada): Encontrar una ruta que visite cada ciudad exactamente una vez y minimice la distancia total recorrida.
3. Problema de la Mochila Fraccionaria: Dado un conjunto de objetos con pesos y valores, y una capacidad máxima de la mochila, maximizar el valor total de los objetos que se pueden llevar.

Dado un conjunto de denominaciones de monedas y una cantidad total, encontrar la mínima cantidad de monedas que sumen esa cantidad.

1. Ordenar las denominaciones de monedas en orden descendente.
2. Inicializar la cantidad total restante como la cantidad dada.
3. Para cada denominación de moneda, tomar tantas monedas como sea posible sin exceder la cantidad total restante.
4. Restar el valor de las monedas tomadas de la cantidad total restante.
5. Repetir hasta que la cantidad total restante sea cero.

1. Ordenar las denominaciones: denominaciones.sort(reverse=True) ordena las denominaciones en orden descendente.
2. Inicializar el resultado: resultado = [] inicializa una lista vacía para almacenar las monedas usadas.
3. Iterar sobre cada denominación: for moneda in denominaciones: itera sobre cada denominación de moneda.
4. Tomar tantas monedas como sea posible: while cantidad >= moneda: toma tantas monedas de la denominación actual como sea posible sin exceder la cantidad total restante.
5. Restar el valor de las monedas tomadas: cantidad -= moneda resta el valor de las monedas tomadas de la cantidad total restante.
6. Verificar si se pudo dar el cambio exacto: if cantidad != 0: verifica si la cantidad total restante es cero. Si no es cero, significa que no se pudo dar el cambio exacto con las denominaciones dadas.

Dado un conjunto de intervalos, encontrar el subconjunto máximo de intervalos no superpuestos.

Dado un conjunto de intervalos [start, end], encontrar el subconjunto máximo de intervalos que no se superpongan.

1. Ordenar los intervalos por su tiempo de finalización.
2. Inicializar el tiempo de finalización del último intervalo seleccionado como negativo infinito.
3. Iterar sobre cada intervalo.
4. Si el tiempo de inicio del intervalo actual es mayor o igual al tiempo de finalización del último intervalo seleccionado, seleccionar el intervalo actual y actualizar el tiempo de finalización del último intervalo seleccionado.

1. Ordenar los intervalos: intervalos.sort(key=lambda x: x[1]) ordena los intervalos por su tiempo de finalización.
2. Inicializar el tiempo de finalización del último intervalo seleccionado: fin_ultimo_intervalo = float('-inf') inicializa el tiempo de finalización del último intervalo seleccionado como negativo infinito.
3. Inicializar el resultado: resultado = [] inicializa una lista vacía para almacenar los intervalos seleccionados.
4. Iterar sobre cada intervalo: for intervalo in intervalos: itera sobre cada intervalo.
5. Seleccionar el intervalo actual: if intervalo[0] >= fin_ultimo_intervalo: selecciona el intervalo actual si su tiempo de inicio es mayor o igual al tiempo de finalización del último intervalo seleccionado.
6. Actualizar el tiempo de finalización del último intervalo seleccionado: fin_ultimo_intervalo = intervalo[1] actualiza el tiempo de finalización del último intervalo seleccionado.

En esta sección, hemos aprendido sobre los algoritmos greedy, sus características y cómo se aplican a problemas específicos. Hemos visto ejemplos prácticos como el problema del cambio de monedas y el problema del intervalo máximo, y hemos implementado soluciones en Python. Los algoritmos greedy son una herramienta poderosa para resolver ciertos tipos de problemas de manera eficiente, aunque no siempre garantizan la solución óptima.