TD d’algorithmique avanc´ee
TD 6 : Algorithmes gloutons
Jean-Michel Dischler et Fr´ed´eric Vivien
Le coˆut de la non panne s`eche
Le professeur Bell conduit une voiture entre Amsterdam et Lisbonne sur l’autoroute E10. Son r´eservoir,
quand il est plein, contient assez d’essence pour faire n kilom`etres, et sa carte lui donne les distances entre
Advertisement
les stations-service sur la route.
1. Donnez une m´ethode efficace grˆace a laquelle Joseph Bell pourra d´eterminer les stations-service ou il
peut s’arrˆeter, sachant qu’il souhaite faire le moins d’arrˆets possible.
2. D´emontrez que votre strat´egie est optimale.
Probleme du sac a dos
Variante « tout ou rien »
Advertisement
Un voleur d´evalisant un magasin trouve n objets, le ie de ces objets valant vi euros et pesant wi kilos, vi
et wi ´etant des entiers. Le voleur veut bien ´evidemment emporter un butin de plus grande valeur possible
mais il ne peut porter que W kilos dans son sac `a dos. Quels objets devra-t-il prendre ?
Variante fractionnaire
Le probl`eme est le mˆeme que le pr´ec´edent, sauf qu’ici le voleur peut ne prendre qu’une fraction d’un
objet et n’est plus oblig´e de prendre l’objet tout entier comme pr´ec´edemment, ou de le laisser.
Advertisement
1. Proposez un algorithme glouton pour la variante fractionnaire.
2. Montrez que cet algorithme est optimal.
3. Quelle est sa complexit´e ?
4. Montrez au moyen d’un contre-exemple que l’algorithme glouton ´equivalent pour la variante « tout ou
rien » n’est pas optimal.
5. Proposez un algorithme de programmation dynamique r´esolvant la variante « tout ou rien ».
Advertisement
6. Quelle est sa complexit´e ?