Curso 2024/2025
Estas notas de sus clases en la Universidad de Stanford de Jessica Su tratan este problema en el primer apartado. Puedes empezar mirando solamente la página 1 como ayuda para entender el problema.
Sea máximoBeneficio(longitud) el máximo valor que se puede obtener con una tubería de esa longitud. El resultado que nos interesa es máximoBeneficio(n).
Por ejemplo, si n vale 7:
máximoBeneficio(7) = max(beneficio[7], beneficio[1] + máximoBeneficio(6), beneficio[2] + máximoBeneficio(5), beneficio[3] + máximoBeneficio(4), beneficio[4] + máximoBeneficio(3), beneficio[5] + máximoBeneficio(2), beneficio[6] + máximoBeneficio(1))
En general:
Si longitud > 1, máximoBeneficio(longitud) = max(beneficio[longitud], max( {beneficio[fragmento] + máximoBeneficio(longitud - fragmento) : fragmento = 1, ... , longitud - 1} )) Si longitud = 1, máximoBeneficio(longitud) = beneficio[1]
Si n vale 7:
máximoBeneficio(7) = max(beneficio[7], máximoBeneficio(1) + máximoBeneficio(6), máximoBeneficio(2) + máximoBeneficio(5), máximoBeneficio(3) + máximoBeneficio(4))
En general:
Si longitud = 1, máximoBeneficio(longitud) = beneficio[1] Si longitud > 1, máximoBeneficio(longitud) = max(beneficio[longitud], max( {máximoBeneficio(fragmento) + máximoBeneficio(longitud - fragmento) : fragmento = 1, ... , longitud / 2} ))