Curso 2023/2024
Sea máximoPremio(i) el máximo premio que el jugador puede obtener con las partidas desde la i hasta la n - 1, ambas inclusive. El resultado que nos piden es máximoPremio(0).
Para obtener máximoPremio(i) el jugador tiene que decidir si participa o no en la partida i y elegir la mejor de las dos opciones:
Si participa en la partida i, la siguiente en la que puede participar si la hay es competición[i].primeraPosterior, con lo que a competición[i].premio puede sumar máximoPremio(competición[i].primeraPosterior).
Si no participa en la partida i, la siguiente en la que puede participar si la hay es la i + 1, pudiendo obtener en ese caso máximoPremio(i + 1).
Escribe las ecuaciones recursivas para calcular máximoPremio(i) siguiendo ese razonamiento, y después comprueba el resultado pulsando el enlace "Más ayuda".
Por supuesto, tu solución debe funcionar correctamente con datos diferentes, no solamente con el primer ejemplo del enunciado.
Por ejemplo, con estos datos del enunciado:
partida | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
inicio | 10 | 11 | 13 | 15 | 16 | 17 | 17 | 18 | 18 |
final | 14 | 18 | 17 | 17 | 19 | 19 | 18 | 19 | 19 |
premio | 7000 | 3000 | 9000 | 5000 | 8000 | 2000 | 4000 | 10000 | 6000 |
primeraPosterior | 3 | 7 | 5 | 5 | -1 | -1 | 7 | -1 | -1 |
podríamos hacer los siguientes cálculos:
máximoPremio(0) = max(7000 + máximoPremio(3), // Si participa en la 0 puede pasar a la 3 máximoPremio(1)) // Si no participa en la 0 puede pasar a la 1 máximoPremio(1) = max(3000 + máximoPremio(7), // Si participa en la 1 puede pasar a la 7 máximoPremio(2)) // Si no participa en la 1 puede pasar a la 2 máximoPremio(2) = max(9000 + máximoPremio(5), // Si participa en la 2 puede pasar a la 5 máximoPremio(3)) // Si no participa en la 2 puede pasar a la 3 máximoPremio(3) = max(5000 + máximoPremio(5), // Si participa en la 3 puede pasar a la 5 máximoPremio(4)) // Si no participa en la 3 puede pasar a la 4 máximoPremio(4) = max(8000, // Si participa en la 4 no puede pasar a ninguna máximoPremio(5)) // Si no participa en la 4 puede pasar a la 5 máximoPremio(5) = max(2000, // Si participa en la 5 no puede pasar a ninguna máximoPremio(6)) // Si no participa en la 5 puede pasar a la 6 máximoPremio(6) = max(4000 + máximoPremio(7), // Si participa en la 6 puede pasar a la 7 máximoPremio(7)) // Si no participa en la 6 puede pasar a la 7 máximoPremio(7) = max(10000, // Si participa en la 7 no puede pasar a ninguna máximoPremio(8)) // Si no participa en la 7 puede pasar a la 8 máximoPremio(8) = 6000 // Caso base
Observa que sería un error decir máximoPremio(4) = 8000
.
Observa también que hay cálculos que se repiten, y de ahí el interés de añadir una tabla para guardar resultados.
Antes de seguir leyendo, intenta escribir tú las ecuaciones generales, a partir de este ejemplo.
// Caso general: Si i < n - 1 y competición[i].primeraPosterior != -1, máximoPremio(i) = max(competición[i].premio + máximoPremio(competición[i].primeraPosterior), máximoPremio(i+1)) // Caso especial: Si i < n - 1 y competición[i].primeraPosterior == -1, máximoPremio(i) = max(competición[i].premio, máximoPremio(i+1)) // Caso base: Si i == n - 1, máximoPremio(i) = competición[i].premio
Con esas ecuaciones, el problema que nos pìden resolver consiste en calcular máximoPremio(0)
.