TP4 - Algorithmes gloutons ¶

A. Ridard

Problème du voyageur¶

Faire l'exercice du cours (diapo 42).

Coder l'algorithme 8 du cours (diapo 43) sous la forme d'une fonction plusProche(villeAct, dist, villesVis).

In [5]:

# réponse

In [6]:

# test

Coder l'algorithme 9 du cours (diapo 44) sous la forme d'une fonction voyageur(nomsVilles, dist, villeDep).

In [7]:

# réponse

In [8]:

# 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)