Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de optimización»
Contenido eliminado Contenido añadido
Línea 194:
; Computar el valor de una solución óptima de forma ordenada:
Para calcular la cantidad de monedas que hacen falta para obtener el monto <math>t</math>, deberá contarse con el valor óptimo para todas las combinaciones de valores que suman <math>t</math>, que serán combinaciones de valores menores que <math>t</math>:
Si calculamos sucesivamente los valores óptimos para los montos menores que <math>t</math>, comenzando desde la unidad, en cada uno de los pasos se deberá utilizar información previamente obtenida.
//inicialización en 1 para los valores que tienen cambio exacto
for(Integer i: monedas)
calculados.set(i.intValue(), new Resultado(i,1));
for(x = 1,resultado = new Resultado(); x < m; x++)
//monto a obtener
{
for(k = 1, menor = x ; k < x; k++)
//divisiones posibles de x
{
valorActual = calculados.get(k).getValor() + calculados.get(x-k).getValor();
if (menor > valorActual)
{
menor = valorActual;
resultado = new Resultado(k, valorActual);
}
}
calculados.set(x, resultado);
}
; Construir una solución óptima a partir de la información computada:
Para construir la solución a partir de la información obtenida, se puede obtener el <math>k</math> de l primer monto:
calculados.get(m).getK()
Y esto significará que la solución será dividir el monto en k y m - k. Luego tendremos que buscar el k óptimo para esos montos:
calculados.get(k).getK()
calculados.get(m - k).getK()
Y así sucesivamente, hasta obtener una a una las unidades necesarias, que irán incrementando la cuenta de cada uno de los tipos de moneda necesarios.
| |||