Diseño y Análisis de Algoritmo

Proyecto Final

Carlos Andrés González Castro

Cód.: 1105675

Universidad de San Buenaventura
Seccional Cali
OBJETIVOS:

Diseñar un algoritmo dinámico que nos informe la ganancia que nos deja invertir dinero en un banco maximizando los intereses.

Calcular la función temporal para el algoritmo

Comprender el comportamiento del algoritmo respecto a tiempo por tamaño.

MARCO TEORICO

Programación Dinámica

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de tres factores importantes como lo son la memoizacion, subproblemas superpuestos y subestructuras óptimas.

La programación …ver más…

Supóngase que los valores de cada función se almacenan en un vector. Este problema tiene una aplicación real muy interesante, en donde fi representa la función de interés que proporciona el banco i, y lo que deseamos es maximizar el interés total al invertir una cantidad determinada de dinero M. Los valores xi van a representar la cantidad a invertir en cada uno de los n bancos.

Solución

Sea fi un vector que almacena el interés del banco i (1 ≤ i n) para una inversión de 1, 2, 3,..., M pesetas. Esto es, fi(j) indicará el interés que ofrece el banco i para j pesetas, con 0 < i ≤ n , 0 < j ≤ M. Para poder plantear el problema como una sucesión de decisiones, llamaremos In(M) al interés máximo al invertir M pesetas en n bancos,
In(M) = f1(x1) + f2(x2) + ... + fn(xn) que es la función a maximizar, sujeta a la restricción x1 +x2 + ... + xn = M.
Veamos cómo aplicar el principio de óptimo. Si In(M) es el resultado de una secuencia de decisiones y resulta ser optima para el problema de invertir una cantidad M en n bancos, cualquiera de sus subsecuencias de decisiones ha de ser también óptima y así la cantidad In–1(M – xn) = f1(x1) + f2(x2) + ... + fn–1(xn–1).
Será también óptima para el subproblema de invertir (M – xn) pesetas en n – 1 bancos. Y por tanto el principio de óptimo nos lleva a plantear la siguiente relación en