Sommaire

Algorithmes gloutons

Les algorithmes gloutons sont les plus simples. Ils ne construisent qu’une seule solution, mais de manière itérative. Ainsi, à chaque pas de temps, on rajoute un élément, le plus prometteur.

Cet algorithme est à adapter à chaque problème. Seul le principe général reste le même.

Ainsi, dans le cas du sac à dos, on va rajouter au fur et à mesure les objets les plus intéressants jusqu’à atteindre la capacité du sac.

Pour cela, on commence par calculer la valeur par kilo de chaque objet :

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

On trie ensuite chaque objet du plus intéressant (la valeur par kilo la plus haute) au moins intéressant. L’ordre obtenu est le suivant :

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

On part d’un sac à dos vide. On ajoute le premier élément d’après le tri, donc l’objet A. Le sac à dos contient alors 4 kg et a une valeur totale de 15.

images/05DP03.png

On ajoute ensuite le premier élément de la liste triée restante. L’objet D ne pèse que 3 kg, on peut donc le mettre dans le sac.

images/05DP04.png

Celui-ci contient alors 7 kg et a une valeur de 25. L’élément suivant est K. Après son ajout, le sac à dos contient ...