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 10:
#Construir una solución óptima a partir de la información computada (este paso puede ser omitido si sólo se requiere el valor y no la solución; de ser realizado, generalmente debe guardarse información adicional).
Dada una cadena de matrices <math>[A_1, A_2,\ldots, A_n]</math>, la tarea es obtener el producto <math>A_1\times A_2\times \ldots \times A_n</math>.
Línea 142:
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.
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:
Sea el monto <math>m</math> de monedas, y suponer que uno de los tipos de monedas susceptibles de usar es la unidad, la solución óptima del problema debe ser alguna de las siguientes:
* Juntar por un lado una moneda, y por el otro <math>m - 1</math>.
* Juntar por un lado dos monedas, y por el otro <math>m - 2</math>.
* ...
* Juntar por un lado <math>\frac{m}{2}</math> monedas, y por el otro <math>\frac{m}{2}</math>.
; Definir recursivamente el valor de una solución:
; Computar el valor de una solución óptima de forma ordenada:
| |||