Algoritmos y Estructuras de Datos (VJ1215)

Sea máximoValor(i, p) el máximo valor que podemos sumar eligiendo entre los objetos del 0 al i, ambos inclusive, sin que el peso de los objetos elegidos supere p. El resultado que nos piden es máximoValor(n - 1, pesoMáximo), siendo n la cantidad de objetos.

Por ejemplo, con estos datos del enunciado:

máximoValor(4, 15) = max(2800 + máximoValor(3, 8), // Coger el objeto 4
                         máximoValor(3, 15))       // No coger el objeto 4
...
	

En general, si i > 0 y peso[i] ≤ p, para obtener máximoValor(i, p) tenemos que decidir si cogemos o no el objeto i y elegir la mejor de las dos opciones:

• Si cogemos el objeto i, podemos sumar valor[i] a lo máximo que podamos conseguir con los objetos del 0 al i - 1 sin que el peso de los elegidos supere p - peso[i].

• Si no cogemos el objeto i, optamos a lo máximo que podamos conseguir con los objetos del 0 al i - 1 sin que el peso de los elegidos supere p.

Completa los casos que faltan, escribe las ecuaciones recursivas para calcular máximoValor(i, p) siguiendo ese razonamiento, y después comprueba el resultado pulsando el enlace "Más ayuda".

Si i > 0 y peso[i] ≤ p,
   máximoValor(i, p) = max(valor[i] + máximoValor(i - 1, p - peso[i]),
                           máximoValor(i - 1, p))

Si i > 0 y peso[i] > p,
   máximoValor(i, p) = máximoValor(i - 1, p)

Si i = 0 y peso[i] ≤ p,
   máximoValor(i, p) = valor[i]

Si i = 0 y peso[i] > p,
   máximoValor(i, p) = 0