Algoritmos y Estructuras de Datos - VJ1215

Ayuda del ejercicio 10 del tema 5.3

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

Solución 1

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]

Solución 2

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} ))