- Utilisés dans les problèmes d’optimisation qui consiste à déterminer les valeurs permettant de minimiser ou pas une fonction objective et satisfaire plusieurs fonctions contraintes.
- Ils correspondent à une solution optimale obtenue en effectuant une suite de meilleurs choix pour chaque étape de l’algorithme
- Pas de retour en arrière lorsque le choix est fait à une étape il ne modifie pas les étapes précédentes.
- Quand un choix est fait on tente de résoudre un problème plus petit = progression descendante
Exemple du rendu de la monnaie:
- C’est un problème algorithmique qui contient un système de monnaie
-> comment rendre une somme donnée de façon optimale?
- On nous demande de minimiser le nombre de pièces et billets.
- on a une liste : system_euro=[500,200,100,50,20,10,5,2,1]
==> Imaginons qu’on doit rendre 83€
- On va faire une boucle while: