Page 81 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 81
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Una posible solución es cualquier conjunto (X X …, X ) que satisfaga (2) y (3). Una solución óptima
1, 2, n
es una solución factible en la cual maximice la ganancia (1). Por ejemplo:
n = 3, M = 20, (P , P , P ) = (25, 24, 15)
1 2 3
(W , W , W ) = (18, 15, 10).
1 2 3
Cuatro posibles soluciones son:
De las cuatro soluciones, la cuarta produce un máximo.
Toda solución óptima llena la mochila al máximo.
Se pueden tener tres estrategias:
a. Escoger los elementos con mayor ganancia (ii).
b. Escoger los elementos con menor peso (iii).
c. Un radio entre P /W (iv).
i i
La estrategia c produce un óptimo y requiere solo O(n).
El algoritmo 3.2 localiza el óptimo siempre y cuando P(i+1) / W(i+1) ≤ P(i) / W(i):
75
