Basado en el libro de texto Introducción a los algoritmos , la corrección de un algoritmo codicioso requiere que un problema tenga dos propiedades:
- propiedad de elección codiciosa
- subestructura óptima
Es fácil encontrar contraejemplos para los que una solución codiciosa falla debido a la falta de la propiedad de elección codiciosa, por ejemplo, el problema de la mochila 0/1. Pero encuentro la otra posibilidad bastante difícil de imaginar. ¿Alguien puede darme un problema y un algoritmo codicioso correspondiente que satisfaga la primera propiedad pero no la segunda?
fuente