PD

PROGRAMACIÓN DINÁMICA
RELACIÓN DE EJERCICIOS Y PROBLEMAS

1. Diseñe algoritmos que permitan resolver eficientemente el problema de la
mochila 0/1 para los siguientes casos:
a. Mochila de capacidad W=15:
Objeto
Peso
Beneficio

1
3
12

2
7
3

3
4
7

4
2
4

5
1
3

6
6
8

3
68
119

4
34
68

5
17
51

6
102
136

4
200
423

5
360
300

6
400
800

b. Mochila de capacidad W=255:
Objeto
Peso
Beneficio

151
204

2
119
51

c. Mochila de capacidad W=1000:
Objeto
Peso
Beneficio

1
130
120

2
570
300

3
140
570

d. ¿Se podría utilizar programación dinámica cuando el peso de un objeto
viene dado por un valor real en vez de entero?
e. Un caso concreto del problema de la mochila puede tener más de una
solución óptima: ¿cómo podríamos darnos cuenta de esto? Diseñe un
algoritmo que devuelva todas lassoluciones óptimas para un caso
concreto del problema de la mochila 0/1.

2. Tenemos un alfabeto Σ = {a,b,c.d} y una relación de orden total Φ definida sobre
los elementos del alfabeto Σ. Sea f(x,y) una función que recibe como entradas
dos elementos de Σ y nos indica si x es el elemento que precede inmediatamente
a y en Φ. Diseñe un algoritmo basado en programación dinámica que, dados dos
elementoscualesquiera del alfabeto, u y v, nos permita determinar si u precede a
v en el orden Φ.
NOTA: En la relación de orden se verifica la propiedad transitiva.

C/ Periodista Daniel Saucedo Aranda s/n, ETSIIT, Universidad de Granada, 18071 Granada Tlf: +34.958.244019 Fax: +34.958.243317

3. Problema del play-off:
Supongamos que dos equipos de baloncesto, Informáticos CB y Basket
Telecom, disputan unplay-off que ganará el primero en conseguir n victorias
(esto es, tendrán que disputar, como mucho 2n-1 partidos):
a. Si suponemos que la probabilidad de que Informáticos CB gane un
partido concreto es un valor fijo P (p.ej. ½), calcule la probabilidad de
que Informáticos CB gane el playoff.
b. Si suponemos que la probabilidad de que un equipo gane un partido
concreto depende de si juega como equipolocal o como visitante, siendo
PL la probabilidad de que gane el partido como local y PV la
probabilidad de que lo gane como visitante, con PL>PV, diseñe un
algoritmo que permita determinar la influencia que supone sobre el
resultado final el hecho de contar con ventaja de campo (esto es, jugar el
primer partido del play-off en casa).
c. ¿Hay alguna diferencia si se intercalan los partidos en casa yfuera con
respecto a jugar el primero en casa, los dos siguientes fuera, otros dos en
casa y así sucesivamente?
CONSEJO: Utilice P(i,j) para representar la probabilidad de que el primer equipo
gane el play-off si necesita ganar i partidos cuando el segundo equipo aún
tendría que ganar j partidos. Antes de comenzar el play-off, por tanto, la
probabilidad de que el primer equipo gane el play-off esP(n,n).

4. Secuencia creciente de máxima longitud:
Sea V un vector con n valores enteros distintos. Diseñe un algoritmo eficiente
basado en programación dinámica para encontrar la secuencia creciente de
máxima longitud en V. Por ejemplo si el vector de entrada es (11, 17, 5, 8, 6, 4,
7, 12, 3), la secuencia creciente de máxima longitud es (5, 6, 7, 12).

5. Problema del viajante de comercioDiseñe un algoritmo basado en programación dinámica para resolver el
problema del viajante de comercio en tiempo O(n22n). ¿Es este algoritmo mejor
que un algoritmo que explore todas las permutaciones posibles?
SUGERENCIA: Defina g(i,S) como la longitud del camino más corto que desde el
nodo i hasta el nodo 1 (donde comenzamos nuestro circuito) que pase
exactamente una vez por cada nodo del conjunto S.Con esta definición, dado un
grafo G(V,E), g(1,V-{1}) nos da la longitud del circuito hamiltoniano minimal.
C/ Periodista Daniel Saucedo Aranda s/n, ETSIIT, Universidad de Granada, 18071 Granada Tlf: +34.958.244019 Fax: +34.958.243317

6. “Multiplicación” de símbolos:
Tenemos un alfabeto Σ = {a,b,c}. Los elementos de Σ tienen la siguiente tabla de
multiplicación, donde las filas muestran...