Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de optimización»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 141:
Y así sucesivamente se pueden encontrar los valores de <math>k</math> que constituirán la solución completa, recorriendo el denominado 'camino hacia atrás'. Esto se puede hacer, porque en cada paso guardamos el valor de <math>k</math> correspondiente.
;Ejemplo: El problema del cambio mínimo
Dado un conjunto de valores de monedas, debe obtenerse la mínima cantidad de monedas que forme determinado monto.
; Caracterizar la estructura de una solución óptima: el problema puede quedar definido en término de sus subproblemas:
; Definir recursivamente el valor de una solución:
; Computar el valor de una solución óptima de forma ordenada:
; Construir una solución óptima a partir de la información computada:
| |||