Révision

Ce qu'il faut savoir

• un algorithme est dit glouton s'il se base sur une méthode gloutonne pour résoudre un problème d'optimisation

• dans une méthode gloutonne, on fait des choix localement optimaux dans l'espoir que ces choix mèneront à une solution globalement optimale. Ces choix ne seront jamais remis en cause au cours de la résolution du problème (pas de retour en arrière possible)

• une méthode gloutonne ne donne pas forcément une solution optimale.

Ce qu'il faut savoir faire

Écrire un programme Python permettant de résoudre un problème d'optimisation (sac à dos ou rendu de monnaie) à l'aide d'un algorithme glouton