Hola buenas, llegué a esa solucion para el algortmk del ej2 pero no me queda claro de si el recorrido esta bien hecho
Hola Maite,
No me queda claro que la recurrencia que estás utilizando esté bien.
Te animás a explicarme qué recurrencia utilizaste y por qué?
Saludos,
Guillermo
No me queda claro que la recurrencia que estás utilizando esté bien.
Te animás a explicarme qué recurrencia utilizaste y por qué?
Saludos,
Guillermo
Claro si. La idea de la recurrencia es esta. Donde la matriz M va a guardar lo que en eso sería OPT
Maite,
La idea general de la recurrencia está bien, pero tiene un par de errores.
En principio quiero marcarte que cuando uno tiene que explicar una recurrencia se debe explicar cómo se divide el problema en subproblemas más pequeños, y debe quedar claro que esta división permite resolver el problema más grande.
En este caso se divide el problema en 2 casos: vendo acciones el día i, o no. En caso de que no, el valor óptimo del problema más grande es efectivamente OPT(i-1, k).
En caso de vender el día i, se deben considerar todos los posibles disparos k, haciendo variar el día de compra, lo que en tu recurrencia llamás c_k. En ese caso el valor óptimo es el máximo sobre todos los { p(v_i) - p(c_k) + OPT(c_k - 1, k - 1) }, con 1 <= c_k <= i. Notá que esto es diferente a lo que tu ponés que es OPT(i-1, k-1).
Luego se debe tomar el máximo entre las dos opciones que mencioné antes, que no es lo mismo que lo que ponés tu, que metiste el OPT(i-1, k) adentro del otro caso.
Espero que esto te ayude, cualquier cosa volvé a consultar.
Saludos,
Guillermo
La idea general de la recurrencia está bien, pero tiene un par de errores.
En principio quiero marcarte que cuando uno tiene que explicar una recurrencia se debe explicar cómo se divide el problema en subproblemas más pequeños, y debe quedar claro que esta división permite resolver el problema más grande.
En este caso se divide el problema en 2 casos: vendo acciones el día i, o no. En caso de que no, el valor óptimo del problema más grande es efectivamente OPT(i-1, k).
En caso de vender el día i, se deben considerar todos los posibles disparos k, haciendo variar el día de compra, lo que en tu recurrencia llamás c_k. En ese caso el valor óptimo es el máximo sobre todos los { p(v_i) - p(c_k) + OPT(c_k - 1, k - 1) }, con 1 <= c_k <= i. Notá que esto es diferente a lo que tu ponés que es OPT(i-1, k-1).
Luego se debe tomar el máximo entre las dos opciones que mencioné antes, que no es lo mismo que lo que ponés tu, que metiste el OPT(i-1, k) adentro del otro caso.
Espero que esto te ayude, cualquier cosa volvé a consultar.
Saludos,
Guillermo
Gracias por la ayuda. Llegué a este resuktado, aun no analice loa tiempos. Esta bien implementado rodo?
Hola Maite,
La recurrencia sigue teniendo algunos de los problemas que mencioné anteriormente.
Además, de la forma que lo planteaste, estás definiendo dos veces OPT, es decir, se está sobreescribiendo la definición.
Luego tu implementación arrastra el error de la recurrencia. Yo te diría que empieces por escribir correctamente la recurrencia siguiendo lo que te señalé en el mensaje anterior, y una vez que confirmemos que es correcta pases a la siguiente parte.
Saludos,
Guillermo
La recurrencia sigue teniendo algunos de los problemas que mencioné anteriormente.
Además, de la forma que lo planteaste, estás definiendo dos veces OPT, es decir, se está sobreescribiendo la definición.
Luego tu implementación arrastra el error de la recurrencia. Yo te diría que empieces por escribir correctamente la recurrencia siguiendo lo que te señalé en el mensaje anterior, y una vez que confirmemos que es correcta pases a la siguiente parte.
Saludos,
Guillermo