TP4 - Algorithmes gloutons ¶

A. Ridard

Problème du voyageur¶

Faire l'exercice du cours (diapo 40).

Coder l'algorithme 8 du cours (diapo 41) sous la forme d'une fonction plusProche(ville, dist, visitees).

In [ ]:

# réponse

In [ ]:

# test

Coder l'algorithme 9 du cours (diapo 42) sous la forme d'une fonction voyageur(villes, dist, depart).

In [ ]:

# réponse

In [ ]:

# test

Problème du sac à dos¶

Coder l'algorithme glouton 3 du cours (diapo 46) sous la forme d'une fonction sac_a_dos(dict_objets, limite) qui retourne la liste des objets choisis.

In [ ]:

# réponse

In [ ]:

# test

dict_objets_test = {'A' : (7,9100), 'B' : (6,7200), 'C' : (4,4800), 'D' : (3,2700), 'E' : (2,2600), 'F' : (1,200)}
limite_test = 10

sac_a_dos(dict_objets_test, limite_test)