Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Sea máximoValorRobable(i) el máximo valor que el ladrón puede obtener con las casas que hay desde la 0 hasta la i, ambas inclusive. El resultado que nos piden es máximoValorRobable(n - 1), siendo n la cantidad de casas.
Para obtener máximoValorRobable(i) el ladrón tiene que decidir si roba o no la casa i y elegir la mejor de las dos opciones:
Si roba la casa i, no puede robar la i - 1 y obtiene valoresCasas[i] más, si existe, lo máximo que pueda acumular hasta la i - 2.
Si no roba la casa i obtiene, si existe, lo máximo que pueda acumular hasta la i - 1.
Escribe las ecuaciones recursivas para calcular máximoValorRobable(i) siguiendo ese razonamiento, y después comprueba el resultado pulsando el enlace "Más ayuda".
Si i > 1, máximoValorRobable(i) = max(valoresCasas[i] + máximoValorRobable(i - 2),
máximoValorRobable(i - 1))
Si i = 1, máximoValorRobable(i) = max(valoresCasas[i],
máximoValorRobable(i - 1))
= max(valoresCasas[1],
valoresCasas[0])
Si i = 0, máximoValorRobable(i) = valoresCasas[0]
Por ejemplo, con valoresCasas = {6000, 10000, 3000, 15000, 4000, 2000, 8000, 5000}:
máximoValorRobable(7) = max(5000 + máximoValorRobable(5), // Robar la casa 7
máximoValorRobable(6)) // No robar la casa 7
máximoValorRobable(6) = max(8000 + máximoValorRobable(4), // Robar la casa 6
máximoValorRobable(5)) // No robar la casa 6
máximoValorRobable(5) = max(2000 + máximoValorRobable(3), // Robar la casa 5
máximoValorRobable(4)) // No robar la casa 5
...
máximoValorRobable(1) = max(10000, // Robar la casa 1
máximoValorRobable(0)) // No robar la casa 1
máximoValorRobable(0) = 6000 // Robar la casa 0