Ayuda-Programacion Dinamica
lapzgolas
08 de Diciembre del 2004
Solicito ayuda a quien buenamente me pudiera ayudar en la tarea de resolver alguno de estos problemas de programacion dinamica, muchas gracias, si alguno de ellos no se entiende o no esta claro agradecere que me escriban a [email protected], gracias LUIS
Ejercicios de Programación dinámica
1. Aplicar el algoritmo de programación dinámica para el problema del cambio de monedas sobre el siguiente ejemplo:
n = 3, P = 9, c = (1, 3, 4). ¿Qué ocurre si multiplicamos P y c por un valor constante, por ejemplo por 1000000?
¿Ocurre lo mismo con el algoritmo voraz? ¿Cómo se podría solucionar?
2. El número de combinaciones de m objetos entre un conjunto de n, denotado por  


 


m
n
, para n ≥ 1 y 0 ≤ m ≤ n, se
puede definir recursivamente por:
 


 


m
n
= 1 Si m = 0 ó m = n
 


 


m
n
=  


 

 −
m
n 1
+  


 


−
−
1
1
m
n
Si 0 < m < n
Conociendo que el resultado puede ser calculado también con la fórmula:
n!/(m!·(n-m)!)
a) Dar una función recursiva para calcular  


 


m
n
, usando la primera de las definiciones. ¿Cuál será el orden de
complejidad de este algoritmo? Sugerencia: la respuesta es inmediata.
b) Diseñar un algoritmo de programación dinámica para calcular  


 


m
n
. Nota: la tabla construida por el algoritmo
es conocida como el triángulo de Pascal. ¿Cuál será el tiempo de ejecución en este caso?
3. Una variante del problema de la mochila es la siguiente. Tenemos un conjunto de enteros (positivos) A = {a1, a2, ...,
an} y un entero K. El objetivo es encontrar si existe algún subconjunto de A cuya suma sea exactamente K.
a) Desarrollar un algoritmo para resolver este problema, utilizando programación dinámica. ¿Cuál es el orden
de complejidad del algoritmo?
b) Mostrar cómo se puede obtener el conjunto de objetos resultantes (en caso de existir solución) a partir de
las tablas utilizadas por el algoritmo.
c) Aplicar el algoritmo sobre el siguiente ejemplo A = {2, 3, 5, 2}, K= 7. ¿Cómo se puede comprobar que la
solución no es única?
4. Considerar el problema del cambio de monedas. Tenemos monedas de n tipos distintos (cada uno con valor ci), y
queremos devolver una cantidad P. Dar un algoritmo, con programación dinámica, para calcular el número de
formas diferentes de devolver la cantidad P (independientemente del número de monedas que se use). ¿Cuál es el
orden de complejidad de este algoritmo?
Aplicar el algoritmo sobre el siguiente ejemplo: n= 4, c= {1, 3, 4, 7}, P= 7.
5. En el problema del cambio de monedas, en lugar de utilizar la ecuación de recurrencia:
Cambio (i, Q) = min (Cambio(i-1, Q), Cambio(i, Q - ci)+1)
Decidimos usar la siguiente:
Cambio (i, Q) = mink=0, ..., Q/c[i] { k + Cambio (i - 1, Q - k·c[i]) }
a) ¿Es correcta esta ecuación de recurrencia para encontrar la solución? Explicar cuál es el significado de esta
fórmula.
b) Suponiendo que modificamos el algoritmo de programación dinámica para usar la segunda fórmula, mostrar
el resultado del algoritmo para el siguiente ejemplo: n= 4, c= {1, 3, 4}, P= 7.
c) Estimar el orden de complejidad del algoritmo. Compararlo con el algoritmo visto en clase.
6. Resolver con programación dinámica el problema del cambio de monedas, pero teniendo una cantidad limitada de
monedas. La cantidad a devolver es C, tenemos monedas de n tipos (cuyos valores están dados en tipos: array[1,..,n]
de entero), y de cada tipo tenemos una cierta cantidad de monedas (almacenadas en un array cantidad: array[1,..,n]
de entero). Es decir, de la moneda de valor tipos[i] podemos dar una cantidad entre 0 y cantidad[i]. Sugerencia:
observar la ecuación del ejercicio anterior.
7. Una agencia de turismo realiza planificaciones de viajes aéreos. Para ir de una ciudad A a B puede ser necesario
coger varios vuelos distintos. El tiempo de un vuelo directo de I a J será T[I, J] (que puede ser distinto de T[J, I]).
Hay que tener en cuenta que si cogemos un vuelo (de A a B) y después otro (de B a C) será necesario esperar un
tiempo de escala adicional en el aeropuerto (almacenado en E[A, B, C]).
a) Diseñar una solución para resolver este problema utilizando programación dinámica. Explicar cómo, a partir de
las tablas, se puede obtener el conjunto de vuelos necesarios para hacer un viaje concreto.
b) Mostrar la ejecución del algoritmo sobre la siguiente matriz T, suponiendo que todos los E[A, B, C] tienen valor
1. ¿Cuál es el orden de complejidad del algoritmo?
T[i, j]
A
B
C D
A - 2 1 3
B 7 - 9 2
C 2 2 - 1
D 3 4 8 -
8. (TG 11.2) Supongamos una serie de n trabajos denominados a, b, c, ... y una tabla B[1..n, 1..n], en la que cada
posición B[i, j] almacena el beneficio de ejecutar el trabajo i y a continuación el trabajo j. Se quiere encontrar la
sucesión de m trabajos que dé un beneficio óptimo. No hay límite en el número de veces que se puede ejecutar un
trabajo concreto.
a) Idear un algoritmo por programación dinámica que resuelva el problema. Para ello, definir un subproblema
(que permita realizar la combinación de problemas pequeños para resolver problemas grandes), especifica la
ecuación de recurrencia para el mismo (con sus casos base) y después describe las tablas necesarias y cómo son
rellenadas.
b) Ejecutar el algoritmo sobre la siguiente tabla, suponiendo que m= 5.
B[i, j] a b c
A 2 2 5
B 4 1 3
C 3 2 2
c) Estimar el tiempo de ejecución del algoritmo. El tiempo estimado ¿es un orden exacto o una cota superior
del peor caso?
9. En una cierta aplicación del problema de la mochila 0/1, los pesos de los objetos están definidos como valores reales.
Por ejemplo, tenemos 5 objetos con pesos p = (3.32, 2.15, 2.17, 3.21, π/2) y beneficios b = (10.2, 9.2, 8.3, 9.1, 6.5) y
capacidad de la mochila M = 7.7. ¿Qué problema ocurre al intentar aplicar el algoritmo de programación dinámica?
Intenta resolverlo de alguna forma y muestra el resultado. ¿La solución encontrada es la óptima?
10. Dada una tabla de tamaño nxn de números naturales, se pretende resolver el problema de obtener el camino de la
casilla (1, 1) a la casilla (n, n) que minimice la suma de los valores de las casillas por las que pasa. En cada casilla (i,
j) habrán sólo dos posibles movimientos: ir hacia abajo (i+1, j), o hacia la derecha (i, j+1).
a) Resolver el problema utilizando programación dinámica. Indica la ecuación de recurrencia usada, con los
casos base necesarios, las tablas para llegar a la solución óptima y para recomponer el camino
correspondiente a esa solución óptima.
b) Mostrar la ejecución del algoritmo sobre la siguiente entrada.
2 8 3 4
5 3 4 5
1 2 2 1
3 4 6 5
c) Formular el principio de optimalidad de Bellman sobre este problema y comprobar si se cumple.
11. Los algoritmos de divide y vencerás y los de programación dinámica se basan en la resolución de un problema en
base a subproblemas. Usando las mismas ecuaciones de recurrencia de los problemas vistos en el tema de
Facultad de Ingeniería de Sistemas e Informática Ciclo: 2004-II
Lic. Jorge Luis Chávez Soto 3
programación dinámina (cambio de monedas, mochila 0/1 y algoritmo de Floyd), diseñar algoritmos que resuelvan
esos problemas pero con divide y vencerás. Compara la complejidad obtenida con los dos tipos de algoritmos.
En los dos primeros casos, ¿por qué los algoritmos no son comparables (al menos de forma directa) con los
algoritmos voraces correspondientes?
12. En el algoritmo para el cambio de monedas visto en clase, ¿es posible que al acabar de ejecutarse obtengamos que
D[n, P] = +∞? En caso afirmativo, ¿qué indica esta situación? Muéstralo con un ejemplo. En caso contrario, ¿por qué
no es posible esa situación?
13. Considerar el siguiente problema: dado un conjunto de números enteros X = {x1, x2, ..., xn} y otro entero P,
queremos encontrar si existe algún subconjunto {y1, ..., yk} de X, tal que P = y1*y2*...*yk.
Resolver el problema utilizando programación dinámica. No es necesario programar el algoritmo, habrá que dar
una ecuación recurrente para resolver el problema, con los casos base, indicar cómo son las tablas que se deben
utilizar y la forma de rellenarlas.
A partir de las tablas, mostrar cómo podemos saber si existe tal conjunto o no, y en caso de existir cómo se
puede obtener el conjunto solución {y1, y2, ..., yk}.
Hacer una estimación del orden de complejidad del algoritmo.
Ejecutar sobre el siguiente ejemplo: X= {2, 4, 3, 9, 10}, P= 18.
Nota: tener en cuenta que el problema no es de optimización, sino de encontrar si existe una solución o no.
14. En el problema de la mochila (igual que en el problema del cambio de monedas) puede existir en general más de una
solución óptima para unas entradas determinadas. ¿Cómo se puede comprobar si una solución óptima es única o no,
suponiendo que hemos resuelto el problema utilizando programación dinámica? Dar un algoritmo para que, a partir
de las tablas resultantes del problema de la mochila, muestre todas las soluciones óptimas existentes.
15. Resolver el siguiente problema usando programación dinámica. Dada una secuencia de enteros positivos (a1, a2, a3,
..., an), encontrar la subsecuencia creciente más larga de elementos no necesariamente consecutivos. Es decir,
encontrar una subsecuencia (ai1, ai2, ..., aik), con (ai1 < ai2 < ...< aik) y (1 ≤ i1 < i2 < ... < ik ≤n). Por ejemplo, para la
siguiente secuencia la solución sería longitud 6 (formada por los números señalados en negrita): 3, 1, 3, 2, 3, 8, 4, 7,
5, 4, 6.
16. Usando la fórmula recursiva para el problema de la mochila 0/1 (vista en clase), escribe un procedimiento que
resuelva el problema pero con divide y vencerás. El cuerpo del procedimiento debe ser:
Mochila(i: entero; M: entero; b, p: array[1..n] de entero): entero
Siendo:
i = Número de objetos a usar (desde 1 hasta i). M = Capacidad de la mochila.
b, p = Beneficio y peso de los objetos. Valor devuelto = Beneficio óptimo.
17. Considera la variante de los números de Fibonacci, que denominaremos números de cuatrinacci, definida a
continuación. El n-ésimo número de cuatrinacci es igual a 3 veces el número (n−1)-ésimo, más 2 veces el (n−2)-
ésimo, menos el n-ésimo número de cuatrinacci. El primer y el segundo números de cuatrinacci valen 1 y 3,
respectivamente. Se pide lo siguiente.
a) Escribe tres posibles implementaciones para el cálculo del n-ésimo número de cuatrinacci usando: un método
descendente de resolución de problemas (por ejemplo, un algoritmo de divide y vencerás), un método
ascendente (por ejemplo, de programación dinámica), y un procedimiento que devuelva el resultado de forma
directa, mediante una simple operación aritmética. Ojo: las implementaciones deben ser muy simples y cortas.
b) Haz una estimación del orden de complejidad de los tres algoritmos del apartado anterior. Compara los órdenes
de complejidad obtenidos, estableciendo una relación de orden entre los mismos.
18. Considerar que en el problema de los ratones (ejercicio 143) todos los pasadizos requieren 1 unidad de tiempo, es
decir P[i, j] = 1 si existe el pasadizo entre i y j. En este experimento se coloca sólo un ratón, en una celda dada S, y
estamos interesados en calcular la probabilidad de que consiga salir del laberinto en el tiempo máximo tmax.
En este caso, suponemos que el ratón se mueve de forma completamente aleatoria por el laberinto y que en cada
instante de tiempo hace un movimiento, excepto si ya ha salido del laberinto, en cuyo caso no volverá a entrar.
Por ejemplo, si en el laberinto de abajo se coloca el ratón en la celda 1, en el instante siguiente estará en la celda 2
con probabilidad 0.5 y en la celda 4 con probabilidad 0.5. Por lo tanto, la probabilidad de que haya salido en el
instante 2 será 0.
Resolver el problema utilizando programación dinámica. Definir la ecuación recurrente, con sus casos base, la
estructura de tablas necesarias y escribir el algoritmo para resolver el problema. Aplicarlo al ejemplo para tmax= 3 y
S=1.
1 2 3
4 5 6
7
8
19. Resolver el siguiente problema con programación dinámica. Tenemos un conjunto de n objetos, cada uno con un
peso p = (p1, p2, ..., pn). El objetivo es repartir los objetos entres dos montones diferentes, de manera que queden lo
más equilibrados posible en peso. Esto es, se debe minimizar la diferencia entre los pesos totales de ambos
montones. Aplicar sobre el ejemplo con n= 4 y p= (2, 1, 3, 4).
Ejercicios de Programación dinámica
1. Aplicar el algoritmo de programación dinámica para el problema del cambio de monedas sobre el siguiente ejemplo:
n = 3, P = 9, c = (1, 3, 4). ¿Qué ocurre si multiplicamos P y c por un valor constante, por ejemplo por 1000000?
¿Ocurre lo mismo con el algoritmo voraz? ¿Cómo se podría solucionar?
2. El número de combinaciones de m objetos entre un conjunto de n, denotado por  


 


m
n
, para n ≥ 1 y 0 ≤ m ≤ n, se
puede definir recursivamente por:
 


 


m
n
= 1 Si m = 0 ó m = n
 


 


m
n
=  


 

 −
m
n 1
+  


 


−
−
1
1
m
n
Si 0 < m < n
Conociendo que el resultado puede ser calculado también con la fórmula:
n!/(m!·(n-m)!)
a) Dar una función recursiva para calcular  


 


m
n
, usando la primera de las definiciones. ¿Cuál será el orden de
complejidad de este algoritmo? Sugerencia: la respuesta es inmediata.
b) Diseñar un algoritmo de programación dinámica para calcular  


 


m
n
. Nota: la tabla construida por el algoritmo
es conocida como el triángulo de Pascal. ¿Cuál será el tiempo de ejecución en este caso?
3. Una variante del problema de la mochila es la siguiente. Tenemos un conjunto de enteros (positivos) A = {a1, a2, ...,
an} y un entero K. El objetivo es encontrar si existe algún subconjunto de A cuya suma sea exactamente K.
a) Desarrollar un algoritmo para resolver este problema, utilizando programación dinámica. ¿Cuál es el orden
de complejidad del algoritmo?
b) Mostrar cómo se puede obtener el conjunto de objetos resultantes (en caso de existir solución) a partir de
las tablas utilizadas por el algoritmo.
c) Aplicar el algoritmo sobre el siguiente ejemplo A = {2, 3, 5, 2}, K= 7. ¿Cómo se puede comprobar que la
solución no es única?
4. Considerar el problema del cambio de monedas. Tenemos monedas de n tipos distintos (cada uno con valor ci), y
queremos devolver una cantidad P. Dar un algoritmo, con programación dinámica, para calcular el número de
formas diferentes de devolver la cantidad P (independientemente del número de monedas que se use). ¿Cuál es el
orden de complejidad de este algoritmo?
Aplicar el algoritmo sobre el siguiente ejemplo: n= 4, c= {1, 3, 4, 7}, P= 7.
5. En el problema del cambio de monedas, en lugar de utilizar la ecuación de recurrencia:
Cambio (i, Q) = min (Cambio(i-1, Q), Cambio(i, Q - ci)+1)
Decidimos usar la siguiente:
Cambio (i, Q) = mink=0, ..., Q/c[i] { k + Cambio (i - 1, Q - k·c[i]) }
a) ¿Es correcta esta ecuación de recurrencia para encontrar la solución? Explicar cuál es el significado de esta
fórmula.
b) Suponiendo que modificamos el algoritmo de programación dinámica para usar la segunda fórmula, mostrar
el resultado del algoritmo para el siguiente ejemplo: n= 4, c= {1, 3, 4}, P= 7.
c) Estimar el orden de complejidad del algoritmo. Compararlo con el algoritmo visto en clase.
6. Resolver con programación dinámica el problema del cambio de monedas, pero teniendo una cantidad limitada de
monedas. La cantidad a devolver es C, tenemos monedas de n tipos (cuyos valores están dados en tipos: array[1,..,n]
de entero), y de cada tipo tenemos una cierta cantidad de monedas (almacenadas en un array cantidad: array[1,..,n]
de entero). Es decir, de la moneda de valor tipos[i] podemos dar una cantidad entre 0 y cantidad[i]. Sugerencia:
observar la ecuación del ejercicio anterior.
7. Una agencia de turismo realiza planificaciones de viajes aéreos. Para ir de una ciudad A a B puede ser necesario
coger varios vuelos distintos. El tiempo de un vuelo directo de I a J será T[I, J] (que puede ser distinto de T[J, I]).
Hay que tener en cuenta que si cogemos un vuelo (de A a B) y después otro (de B a C) será necesario esperar un
tiempo de escala adicional en el aeropuerto (almacenado en E[A, B, C]).
a) Diseñar una solución para resolver este problema utilizando programación dinámica. Explicar cómo, a partir de
las tablas, se puede obtener el conjunto de vuelos necesarios para hacer un viaje concreto.
b) Mostrar la ejecución del algoritmo sobre la siguiente matriz T, suponiendo que todos los E[A, B, C] tienen valor
1. ¿Cuál es el orden de complejidad del algoritmo?
T[i, j]
A
B
C D
A - 2 1 3
B 7 - 9 2
C 2 2 - 1
D 3 4 8 -
8. (TG 11.2) Supongamos una serie de n trabajos denominados a, b, c, ... y una tabla B[1..n, 1..n], en la que cada
posición B[i, j] almacena el beneficio de ejecutar el trabajo i y a continuación el trabajo j. Se quiere encontrar la
sucesión de m trabajos que dé un beneficio óptimo. No hay límite en el número de veces que se puede ejecutar un
trabajo concreto.
a) Idear un algoritmo por programación dinámica que resuelva el problema. Para ello, definir un subproblema
(que permita realizar la combinación de problemas pequeños para resolver problemas grandes), especifica la
ecuación de recurrencia para el mismo (con sus casos base) y después describe las tablas necesarias y cómo son
rellenadas.
b) Ejecutar el algoritmo sobre la siguiente tabla, suponiendo que m= 5.
B[i, j] a b c
A 2 2 5
B 4 1 3
C 3 2 2
c) Estimar el tiempo de ejecución del algoritmo. El tiempo estimado ¿es un orden exacto o una cota superior
del peor caso?
9. En una cierta aplicación del problema de la mochila 0/1, los pesos de los objetos están definidos como valores reales.
Por ejemplo, tenemos 5 objetos con pesos p = (3.32, 2.15, 2.17, 3.21, π/2) y beneficios b = (10.2, 9.2, 8.3, 9.1, 6.5) y
capacidad de la mochila M = 7.7. ¿Qué problema ocurre al intentar aplicar el algoritmo de programación dinámica?
Intenta resolverlo de alguna forma y muestra el resultado. ¿La solución encontrada es la óptima?
10. Dada una tabla de tamaño nxn de números naturales, se pretende resolver el problema de obtener el camino de la
casilla (1, 1) a la casilla (n, n) que minimice la suma de los valores de las casillas por las que pasa. En cada casilla (i,
j) habrán sólo dos posibles movimientos: ir hacia abajo (i+1, j), o hacia la derecha (i, j+1).
a) Resolver el problema utilizando programación dinámica. Indica la ecuación de recurrencia usada, con los
casos base necesarios, las tablas para llegar a la solución óptima y para recomponer el camino
correspondiente a esa solución óptima.
b) Mostrar la ejecución del algoritmo sobre la siguiente entrada.
2 8 3 4
5 3 4 5
1 2 2 1
3 4 6 5
c) Formular el principio de optimalidad de Bellman sobre este problema y comprobar si se cumple.
11. Los algoritmos de divide y vencerás y los de programación dinámica se basan en la resolución de un problema en
base a subproblemas. Usando las mismas ecuaciones de recurrencia de los problemas vistos en el tema de
Facultad de Ingeniería de Sistemas e Informática Ciclo: 2004-II
Lic. Jorge Luis Chávez Soto 3
programación dinámina (cambio de monedas, mochila 0/1 y algoritmo de Floyd), diseñar algoritmos que resuelvan
esos problemas pero con divide y vencerás. Compara la complejidad obtenida con los dos tipos de algoritmos.
En los dos primeros casos, ¿por qué los algoritmos no son comparables (al menos de forma directa) con los
algoritmos voraces correspondientes?
12. En el algoritmo para el cambio de monedas visto en clase, ¿es posible que al acabar de ejecutarse obtengamos que
D[n, P] = +∞? En caso afirmativo, ¿qué indica esta situación? Muéstralo con un ejemplo. En caso contrario, ¿por qué
no es posible esa situación?
13. Considerar el siguiente problema: dado un conjunto de números enteros X = {x1, x2, ..., xn} y otro entero P,
queremos encontrar si existe algún subconjunto {y1, ..., yk} de X, tal que P = y1*y2*...*yk.
Resolver el problema utilizando programación dinámica. No es necesario programar el algoritmo, habrá que dar
una ecuación recurrente para resolver el problema, con los casos base, indicar cómo son las tablas que se deben
utilizar y la forma de rellenarlas.
A partir de las tablas, mostrar cómo podemos saber si existe tal conjunto o no, y en caso de existir cómo se
puede obtener el conjunto solución {y1, y2, ..., yk}.
Hacer una estimación del orden de complejidad del algoritmo.
Ejecutar sobre el siguiente ejemplo: X= {2, 4, 3, 9, 10}, P= 18.
Nota: tener en cuenta que el problema no es de optimización, sino de encontrar si existe una solución o no.
14. En el problema de la mochila (igual que en el problema del cambio de monedas) puede existir en general más de una
solución óptima para unas entradas determinadas. ¿Cómo se puede comprobar si una solución óptima es única o no,
suponiendo que hemos resuelto el problema utilizando programación dinámica? Dar un algoritmo para que, a partir
de las tablas resultantes del problema de la mochila, muestre todas las soluciones óptimas existentes.
15. Resolver el siguiente problema usando programación dinámica. Dada una secuencia de enteros positivos (a1, a2, a3,
..., an), encontrar la subsecuencia creciente más larga de elementos no necesariamente consecutivos. Es decir,
encontrar una subsecuencia (ai1, ai2, ..., aik), con (ai1 < ai2 < ...< aik) y (1 ≤ i1 < i2 < ... < ik ≤n). Por ejemplo, para la
siguiente secuencia la solución sería longitud 6 (formada por los números señalados en negrita): 3, 1, 3, 2, 3, 8, 4, 7,
5, 4, 6.
16. Usando la fórmula recursiva para el problema de la mochila 0/1 (vista en clase), escribe un procedimiento que
resuelva el problema pero con divide y vencerás. El cuerpo del procedimiento debe ser:
Mochila(i: entero; M: entero; b, p: array[1..n] de entero): entero
Siendo:
i = Número de objetos a usar (desde 1 hasta i). M = Capacidad de la mochila.
b, p = Beneficio y peso de los objetos. Valor devuelto = Beneficio óptimo.
17. Considera la variante de los números de Fibonacci, que denominaremos números de cuatrinacci, definida a
continuación. El n-ésimo número de cuatrinacci es igual a 3 veces el número (n−1)-ésimo, más 2 veces el (n−2)-
ésimo, menos el n-ésimo número de cuatrinacci. El primer y el segundo números de cuatrinacci valen 1 y 3,
respectivamente. Se pide lo siguiente.
a) Escribe tres posibles implementaciones para el cálculo del n-ésimo número de cuatrinacci usando: un método
descendente de resolución de problemas (por ejemplo, un algoritmo de divide y vencerás), un método
ascendente (por ejemplo, de programación dinámica), y un procedimiento que devuelva el resultado de forma
directa, mediante una simple operación aritmética. Ojo: las implementaciones deben ser muy simples y cortas.
b) Haz una estimación del orden de complejidad de los tres algoritmos del apartado anterior. Compara los órdenes
de complejidad obtenidos, estableciendo una relación de orden entre los mismos.
18. Considerar que en el problema de los ratones (ejercicio 143) todos los pasadizos requieren 1 unidad de tiempo, es
decir P[i, j] = 1 si existe el pasadizo entre i y j. En este experimento se coloca sólo un ratón, en una celda dada S, y
estamos interesados en calcular la probabilidad de que consiga salir del laberinto en el tiempo máximo tmax.
En este caso, suponemos que el ratón se mueve de forma completamente aleatoria por el laberinto y que en cada
instante de tiempo hace un movimiento, excepto si ya ha salido del laberinto, en cuyo caso no volverá a entrar.
Por ejemplo, si en el laberinto de abajo se coloca el ratón en la celda 1, en el instante siguiente estará en la celda 2
con probabilidad 0.5 y en la celda 4 con probabilidad 0.5. Por lo tanto, la probabilidad de que haya salido en el
instante 2 será 0.
Resolver el problema utilizando programación dinámica. Definir la ecuación recurrente, con sus casos base, la
estructura de tablas necesarias y escribir el algoritmo para resolver el problema. Aplicarlo al ejemplo para tmax= 3 y
S=1.
1 2 3
4 5 6
7
8
19. Resolver el siguiente problema con programación dinámica. Tenemos un conjunto de n objetos, cada uno con un
peso p = (p1, p2, ..., pn). El objetivo es repartir los objetos entres dos montones diferentes, de manera que queden lo
más equilibrados posible en peso. Esto es, se debe minimizar la diferencia entre los pesos totales de ambos
montones. Aplicar sobre el ejemplo con n= 4 y p= (2, 1, 3, 4).
Sentido com?
08 de Diciembre del 2004
JA JA JA JA, Buen chiste ;)
P.D.
No le hacemos la tarea a nadie.
P.D.
No le hacemos la tarea a nadie.
Forastero
08 de Diciembre del 2004
Hola.
Te hago todos los programas por 3000 (requiere algo de tiempo).
Un saludo.
Te hago todos los programas por 3000 (requiere algo de tiempo).
Un saludo.