Algoritmos Programacion Dinamica

Algoritmos Programaci´n Din´mica
o
a

1. Aplicar el algoritmo de programaci´n din´mica para el problema del cambio de monedas sobre el siguiente
o
a
ejemplo: n = 3 (n´mero de tipos de monedas), P = 9 (cantidad), c = (1, 3, 4) (tipos de monedas).
u
¿Qu´ ocurre si multiplicamos P y c por un valor constante, por ejemplo, por 1000000? ¿Ocurre lo mismo
e
con el algoritmo greedy? ¿C´mo sepodr´ solucionar?
o
ıa
2. Desarrolla un algoritmo de programaci´n din´mica para resolver el problema de la mochila 0-1 con la
o
a
variante de que, de cada objeto, contamos con un cierto n´mero de copias.
u
3. Modificar la soluci´n en programaci´n din´mica del problema del cambio, para el caso en que tengamos
o
o
a
un n´mero limitado de monedas de cada tipo.
u
4. Sea V un vector con nvalores enteros distintos. Dise˜e un algoritmo eficiente basado en programaci´n
n
o
din´mica para encontrar la secuencia creciente de m´xima longitud en V . Por ejemplo si el vector de
a
a
entrada es (11, 17, 5, 8, 6, 4, 7, 12, 3), la secuencia creciente de m´xima longitud es (5, 6, 7, 12).
a
5. A lo largo de un r´ hay n aldeas. En cada aldea, se puede alquilar una canoa que se puede devolveren
ıo
cualquier otra aldea que est´ a favor de corriente (resulta casi imposible remar a contra corriente). Para
e
todo posible punto de partida i y para todo posible punto de llegada j, se conoce el coste de alquilar una
canoa desde i hasta j. Sin embargo, puede ocurrir que el coste del alquiler desde i hasta j sea mayor que el
coste total de una serie de alquileres m´s breves. En talcaso, se puede devolver la primera canoa en alguna
a
aldea k situada entre i y j y seguir el camino en una nueva canoa (no hay costes adicionales por cambiar
de canoa de esta manera). Dise˜a un algoritmo basado en programaci´n din´mica para determinar el
n
o
a
coste m´
ınimo del viaje en canoa desde todos los puntos posibles de partida i a todos los posibles puntos
de llegada j. Aplique dichoalgoritmo en la resoluci´n del siguiente caso:
o
1
2
3
4
5

1 2
0 17
∞ 0
∞ ∞
∞ ∞
∞ ∞

3 4 5
8 16 20
12 6 15
0 12 16
∞ 0 15
∞ ∞ 0

6. Supongamos que existen n bancos en los que podemos invertir, y disponemos de una cantidad M para
invertirla. Cada banco nos proporciona intereses seg´n una funci´n mon´tona creciente, fi (x), donde x es
u
o
o
el importe a invertir e i elbanco en el que se invierte. Que fi es mon´tona creciente significa que x ≥ y
o
implica que fi (x) ≥ fi (y). Dise˜a un algoritmo de programaci´n din´mica que encuentre la inversi´n
n
o
a
o
o
´ptima: la cantidad que se debe invertir en cada banco para maximizar los intereses obtenidos.
Dicho de otra manera, dadas n funciones f1 , f2 , . . ., fn y un entero positivo M , deseamos maximizar lafunci´n f1 (x1 ) + f2 (x2 ) + · · · + fn (xn ) sujeta a la restricci´n x1 + x2 + · · · + xn = M , donde fi (0) = 0
o
o
(i = 1, . . . , n), xi son numeros naturales, y todas las funciones son mon´tonas crecientes, es decir, x ≥ y
o
implica que fi (x) ≥ fi (y).
7. Una compa˜´ de ferrocarriles sirve n estaciones S1 , . . . , Sn y trata de mejorar su servicio al cliente
nıa
medianteterminales de informaci´n. Dadas una estaci´n origen So y una estaci´n destino Sd , un terminal
o
o
o
debe ofrecer (inmediatamente) la informaci´n sobre el horario de los trenes que hacen la conexi´n entre So
o
o
y Sd y que minimizan el tiempo de trayecto total. Necesitamos implementar un algoritmo que realice esta
tarea a partir de la tabla con los horarios, suponiendo que las horas de salida delos trenes coinciden con
las de sus llegadas (es decir, que no hay tiempos de espera) y que, naturalmente, no todas las estaciones
est´n conectadas entre s´ por l´
a
ı
ıneas directas; as´ en muchos casos hay que hacer transbordos aunque se
ı,
supone que tardan tiempo cero en efectuarse.

1

8. Pepe Casanova es un lig´n de los de anta˜o, que intenta encandilar a las chicas con...