Programaciondinamica

Ejercicio 1. Programaci´n din´mica o a
[ITIS/ITIG, Feb 2007] Dada una cantidad de dinero C , deseamos encontrar el m´ ınimo n´mero de u monedas que cubra exactamente, si es posible, esta cantidad. Para ello conocemos los valores de los N tipos de monedas y el n´mero de monedas u disponibles de cada tipo. Dise˜a un algoritmo din´mico que resuelva el n a problema detallando lo siguiente: Laestructura de c´lculos intermedios. (0,5 puntos) a La relaci´n recursiva. (1 punto) o La funci´n o procedimiento que implemente este algoritmo. (2,5 o puntos).

Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u

1 / 32

Soluci´n Ejercicio 1. Programaci´n din´mica o o a
Este ejercicio es muy parecido al que hemos visto anteriormente de devoluci´n del cambio o La diferencia es que el n´mero demonedas disponibles de cada tipo u es limitado Recordando el caso de estudio de devoluci´n del cambio, la expresi´n o o recurrente que lo defin´ era: ıa C [i, j] = m´ ın(C [i − 1, j], 1 + C [i, j − di ]) De los dos accesos recurrentes de la expresi´n anterior: o
a) C [i − 1, j] corresponde con la decisi´n de no tomar ninguna moneda de o valor di . Este caso no modifica el n´mero de monedas utilizado parau obtener C [i, j]. No afecta la limitaci´n en el n´mero de monedas. o u b) 1 + C [i, j − di ] corresponde con la selecci´n de una moneda de valor di o (al menos). Este caso s´ modifica el n´mero de monedas que se ı u necesita para obtener C [i, j] en funci´n de C [i, j − di ], pues se utiliza o una moneda de valor di .
Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u 2 / 32

Soluci´n Ejercicio1. Programaci´n din´mica (cont.) o o a
Una posible soluci´n es considerar tantos casos como monedas de o valor di est´n disponibles, y despu´s calcular el m´ e e ınimo de todos ellos C [i, j] = m´ (k + C [i − 1, j − di ∗ k]) ın
0≤k≤mi

donde mi es el n´mero de monedas disponibles de valor di . u La recurrencia completa es: 
 0    +∞      +∞               

C (i, j)=

0≤k≤mi

si j = 0 si j < 0 si i = 1 y (j < di o j > di ∗ mi o j mod di = 0) j/di si i = 1 y j mod di = 0 y j ≤ di ∗ mi m´ (k + C [i − 1, j − di ∗ k]) en otro caso ın

Para cada uno de los valores de k (desde 1 hasta mi ) se considera tomar las k monedas de valor di , en lugar de hacerlo de una en una como en la versi´n original del problema de devoluci´n del cambio o o
Yolanda Garc´ Jes´sCorreas (DSIC - UCM) ıa, u 3 / 32

Soluci´n Ejercicio 1. Programaci´n din´mica (cont.) o o a
fun monedas2(d[1..N], m[1..N],Cant) crear C[1..N,0..Cant] desde i← 1 hasta N hacer C[i,0] ← 0 desde i← 1 hasta N hacer desde j← 1 hasta Cant hacer si i=1 Y j k+C[i-1,j-k*d[i]] entonces min ← k+C[i-1,j-k*d[i]] fin desde C[i,j] ← min fin si fin desde fin desde devolver C[N,Cant] fin fun
Yolanda Garc´ Jes´sCorreas (DSIC - UCM) ıa, u 4 / 32

Ejercicio 2. Programaci´n din´mica o a
[ITIS/ITIG, Sep 2007] En el departamento de una empresa de traducciones se desea hacer traducciones de textos entre varios idiomas. Se dispone de algunos diccionarios. Cada diccionario permite la traducci´n (bidireccional) o entre dos idiomas. En el caso m´s general, no se dispone de diccionarios a para cada par deidiomas por lo que es preciso realizar varias traducciones. Dados N idiomas y M diccionarios, determina si es posible realizar la traducci´n entre dos idiomas dados y, en caso de ser posible, determina la o cadena de traducciones de longitud m´ ınima. Dise˜a un algoritmo din´mico que resuelva el problema detallando lo n a siguiente: 1. La estructura de c´lculos intermedios utilizada (0,5 puntos). a 2.La relaci´n recursiva entre subproblemas (0,5 puntos). o 3. El procedimiento o funci´n que implemente el algoritmo (2 puntos). o

Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u

5 / 32

Ejercicio 2. Programaci´n din´mica (cont.) o a

Ejemplo 1: Traducir del lat´ al arameo disponiendo de los siguientes diccionarios: ın lat´ ın-griego, griego-etrusco, griego-dem´tico, dem´tico-arameo o o...