Algoritmos y Estructuras de Datos - VJ1215

Ayuda del ejercicio 3 del tema 5.3

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.

Más ayuda

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.

Más ayuda (2)

// 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).