Algorithme glouton

Algorithme glouton

Principe :

Le principe de l’algorithme glouton (greedy algorithm) :

 faire toujours un choix localement optimal dans l’espoir que ce choix mènera à une solution globalement optimale.

Exercice :

 Comment rendre la monnaie. Nous considérons des pièces de monnaie de 1, 2, et 5 centimes. Notons  \(N\left( x \right)\)  le nombre minimum de pièces pour obtenir  \(x\) centimes.

 Question 1 :

Quelle est la valeur de \(N\left( 0 \right),\ N\left( 1 \right),\ N\left( 2 \right),\ N\left( 3 \right),\ N\left( 4 \right),\ N\left( 5 \right)\)  ?

Correction

\(~N\left( 0 \right)\ = \ 0,\ N\left( 1 \right)\ = \ 1,\ N\left( 2 \right)\ = \ 2,\ N\left( 3 \right)\ = \ 2,\ N\left( 4 \right)\ = \ 2,\ N\left( 5 \right)\ = \ 1\)

Question 2 :

Donner un algorithme qui calcule \(N\left( x \right)\)  et sa complexité en termes d’opérations.

 Correction Algorithme Glouton :

·        Trier les types de pièces par valeur décroissante.

·        Pour chaque valeur de pièce, maximiser le nombre de pièces choisies.

Plus formellement, soit  \(R\)  la somme restante, initialisé à \(S\) .

 Pour chaque  \(~v_{i}\)  ,\(~c_{i} = \frac{\left( {R - R~{mod}\,\,\, v_{i}} \right)}{v_{i}}\) , on prend \(c_{i}\)   \(v_{i}\)

Et on pose   \(\left. R\leftarrow R - v_{i} \times c_{i} \right.\)

Pour prouver l’optimalité de l’algorithme glouton avec les  \(5,\text{2}\)  et \(1\) :

·        Au plus une pièce de \(1\)  (sinon une   \(2\) )

·        Au plus deux pièces de \(2\)  (sinon une  \(5\)  et une de \(1\) )

·        Le nombre de pièces de\(5\) est   \(\frac{x - x~{mod}~5}{x}\) 

·        Conclure avec ce qui précède

Question 3 :

 Appliquer cet algorithme qui  \(N\left( 14 \right)\)  en considérant maintenant qu’on dispose des pièces de monnaies de \(1,\text{5}\)  et\(10\)  centimes. Que constatez-vous ?

Correction :

Si on utilise l’algorithme précédent, alors on utilise une pièce  \(10\)  et quatre pièces  \(1\) .

Programmme en python :


_images/insglouton01.PNG

Résultat  :


Donner un somme à payer en € : 45.21

Pour payer 45 , 21 € ; il faut 2x20 € 1x5 € 1x0.20 € 1x0.01 €