Curso 2022/2023
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 los datos del enunciado:
objeto | 0 | 1 | 2 | 3 |
---|---|---|---|---|
peso | 100 | 40 | 50 | 80 |
valor | 5000 | 3600 | 4500 | 8000 |
máximoValor(3, 100) = max(8000 + máximoValor(2, 20), // Coger el objeto 3 máximoValor(2, 100)) // No coger el objeto 3 ...
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