Para muchos problemas de optimización un algoritmo de programación dinámica es overkill. Un algoritmo goloso (greedy) siempre toma la decisión que parece más acertada en el momento, es decir, una decisión óptima local, con la esperanza de que ésta lleve a una solución óptima global.
Los algoritmos greedy toman la decisión que parece mejor en el momento. Esta estrategia no siempre produce soluciones óptimas, pero para algunos problemas resulta muy útil.
Usualmente al desarrollar algoritmos greedy seguimos los siguientes pasos:
La greedy-choice property consiste en la posibilidad de armar una solución óptima global basándonos en decisiones óptimas locales. Es decir, cuando contemplamos qué decisión tomar, tomamos la que parece óptima en el momento, sin preocuparnos por los resultados de los otros subproblemas.
Esta es la gran diferencia entre los algoritmos de programación dinámica y los greedy: la decisión greedy no depende de los resultados de subproblemas a resolver más adelante. Puede depender de qué decisiones tomamos anteriormente, pero no de las soluciones a otros subproblemas ni de decisiones futuras.
Un problema posee subestructura óptima si sus soluciones óptimas contienen soluciones óptimas a subproblemas del problema original.
En general al argumentar que un problema exhibe subestructura óptima para aplicar un algoritmo greedy, necesitamos mostrar que una solución óptima al problema combinada con la decisión greedy que acabamos de tomar constituyen una soución óptima al problema original. Implícitamente al hacer esto estamos haciendo inducción en los subproblemas.