Exemple d’algorithme glouton : le rendu de monnaie

En informatique, on rencontre souvent des problèmes d’optimisation comme celui mis en œuvre dans le rendu de monnaie. Les algorithmes gloutons sont couramment utilisés pour les résoudre.

I. Le rendu de monnaie

On veut programmer une caisse automatique pour qu’elle rende la monnaie de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets.

La valeur des pièces et billets à disposition sont : 1, 2, 5, 10, 20, 50, 100 et 200 euros. On dispose d’autant d’exemplaires qu’on le souhaite de chaque pièce et billet.

Exemple : Anaïs veut acheter un objet qui coûte 53 euros. Elle paye avec un billet de 100 euros. La caisse automatique doit lui rendre 47 euros.

La meilleure façon de rendre la monnaie est de le faire avec deux billets de 20, un billet de 5 et une pièce de 2 euros.

II. Résolution du problème de rendu de monnaie

1) La force brute

La solution naïve consiste à énumérer toutes les solutions possibles puis choisir la solution optimale, celle qui minimise le nombre de pièces et de billets. On peut totaliser 47 euros de différentes façons, par exemple :

Cette méthode permet de trouver la solution optimale globale au problème, mais le nombre de possibilités est très important. L’utilisation d’un tel algorithme ici est très coûteux en temps de calcul.

2) L’algorithme glouton

Le principe de l’algorithme glouton

Utiliser un algorithme glouton consiste à optimiser la résolution d’un problème en utilisant l’approche suivante : on procède étape par étape, en faisant, à chaque étape, le choix qui semble le meilleur, sans jamais remettre en question les choix passés.

Application au rendu de monnaie

Dans l’exemple du problème de rendu de monnaie, on commence par rendre la pièce ou le billet de la plus grande valeur possible, c’est-à-dire dont la valeur est inférieure à la somme à rendre. On déduit alors cette valeur de la somme à rendre, ce qui conduit à un problème de plus petite taille. On recommence ainsi jusqu’à obtenir une somme nulle.

Données : la somme à rendre et la liste des pièces et billets à disposition.

Résultat : une liste des pièces et billets à rendre.

Algorithme :

• initialiser monnaie à la liste vide ;

• initialiser somme_restante à somme ;

• tant que la somme_restante est strictement positive :

* on choisit dans liste la plus grande valeur qui ne dépasse pas la somme restante,

* on ajoute cette valeur à monnaie,

* somme restante = somme restante - valeur choisie ;

• renvoyer monnaie.

3) Solution du problème de rendu de monnaie

Dans notre exemple, on a :

somme = 47

liste = [1, 2, 5, 10, 20, 50, 100, 200]

L’algorithme permet de résoudre le problème étape par étape :

Résultat : [20, 20, 5, 2].

Un algorithme glouton permet de trouver une solution optimale locale au problème, mais pas toujours une solution optimale globale.

Par exemple, si notre caisse automatique doit rendre une somme de 63 euros, mais qu’elle ne dispose plus de billets de 5 euros ni de 10 euros.

somme = 63

liste = [1, 2, 20, 50, 100, 200]

L’algorithme glouton donne comme résultat :

resultat = [50, 2, 2, 2, 2, 2, 2, 1]

Alors que la solution optimale globale est :

solution_optimale_globale = [20, 20, 20, 2, 1]