Algoritmos voraces Algoritmo:voraz

Los algoritmos voraces son los más sencillos. No construyen más que una única solución, pero de manera iterativa. Así, conforme avanza el tiempo, se agrega un elemento, el más prometedor.

Este algoritmo debe adaptarse a cada problema. Solo se mantiene el principio general.

De este modo, en el caso de la mochila, agregaremos conforme avancemos los objetos más interesantes hasta alcanzar la capacidad de la mochila.

Para ello, empezamos calculando el valor por kilo de cada objeto:

A)

4kg - 15 : 3.75

B)

7 kg - 15 : 2.14

C)

10 kg - 20 : 2

D)

3 kg - 10 : 3.33

E)

6 kg - 11 : 1.83

F)

12 kg - 16 : 1.33

G)

11 kg - 12 : 1.09

H)

16 kg - 22 : 1.38

I)

5 kg - 12 : 2.4

J)

14 kg - 21 : 1.5

K)

4 kg - 10 : 2.5

L)

3 kg - 7 : 2.33

Ordenamos, a continuación, cada objeto desde el más interesante (el valor por kilo mayor) hasta el menos interesante. Se obtiene el orden siguiente:

A - D - K - I - L - B - C - E - J - H - F - G

Se parte de una mochila vacía. Se agrega el primer elemento tras la ordenación, en este caso el objeto A. La mochila contiene, ahora, 4 kg y posee un valor total de 15.

images/c05f02.PNG

Se agrega, a continuación, el primer elemento de la lista ordenada restante. El objeto D no pesa más que 3 kg, de modo que es posible meterlo en la mochila.

images/c05f03.PNG

Esta contiene, ahora, 7 kg y posee un valor de 25. El siguiente elemento es K. Una vez se agrega, la mochila contiene 11 kg y posee un valor igual a 35. El cuarto elemento es I.

images/c05f04.PNG

Tenemos 16 kg y un valor total de 47. El siguiente elemento...

Si desea saber más, le proponemos el siguiente libro:
couv_DPT2INT.png
60-signet.svg
Versión impresa
20-ecran_lettre.svg
Versión online
41-logo_abonnement.svg
En ilimitado con la suscripción ENI
130-boutique.svg
En la tienda oficial de ENI
Anterior
Optimización y mínimos
Siguiente
Descenso por gradiente