Rendre la monnaie avec le moins de pièces possible, remplir un sac en emportant le plus de valeur : ce sont des problèmes d’optimisation. Essayer toutes les possibilités devient vite impossible. Un algorithme glouton construit une solution pas à pas, en faisant à chaque étape le choix qui semble le meilleur sur le moment. C’est rapide… mais pas toujours optimal.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Reconnaître un problème d’optimisation et la stratégie gloutonne
- Écrire et dérouler l’algorithme glouton du rendu de monnaie
- Appliquer une stratégie gloutonne au problème du sac à dos
- Savoir qu’un algorithme glouton ne donne pas toujours la solution optimale et trouver un contre-exemple
1. Le principe glouton
Algorithme glouton : Algorithme qui construit une solution étape par étape en faisant à chaque fois le choix localement optimal (le meilleur à cet instant), sans jamais revenir en arrière.
Avantage : il est simple et rapide. Une recherche exhaustive, elle, doit souvent examiner un nombre énorme de cas : avec n objets, il y a 2ⁿ façons d’en choisir une partie (plus d’un million pour 20 objets). Inconvénient : la solution obtenue n’est pas forcément la meilleure.
2. Le rendu de monnaie
Problème : rendre une somme avec le moins de pièces et billets possible. Stratégie gloutonne : rendre à chaque fois la plus grande valeur possible qui ne dépasse pas la somme restante.
def rendu_monnaie(somme, pieces):
"""pieces : valeurs disponibles, triées par ordre décroissant."""
rendu = []
for p in pieces:
while somme >= p:
rendu.append(p)
somme = somme - p
return rendu
euros = [200, 100, 50, 20, 10, 5, 2, 1]Rendre 87 € avec le système de l’euro
- 87 ≥ 50 : on rend 50, il reste 37.
- 37 ≥ 20 : on rend 20, il reste 17.
- 17 ≥ 10 : on rend 10, il reste 7.
- 7 ≥ 5 : on rend 5, il reste 2 ; puis on rend 2, il reste 0.
rendu_monnaie(87, euros) renvoie [50, 20, 10, 5, 2] : 5 pièces et billets.
3. Le problème du sac à dos
Un sac supporte au plus 10 kg. On veut emporter des objets de valeur totale maximale sans dépasser cette capacité.
| Objet | Poids (kg) | Valeur (€) | Valeur par kg |
|---|---|---|---|
| A | 7 | 42 | 6 |
| B | 3 | 12 | 4 |
| C | 4 | 40 | 10 |
| D | 5 | 25 | 5 |
Stratégie gloutonne : meilleur rapport valeur/poids d’abord
- Ordre des rapports : C (10), A (6), D (5), B (4).
- C (4 kg) : on le prend, 4 kg utilisés.
- A (7 kg) : 4 + 7 = 11 > 10, on ne le prend pas.
- D (5 kg) : 4 + 5 = 9 ≤ 10, on le prend.
- B (3 kg) : 9 + 3 = 12 > 10, on ne le prend pas.
On emporte C et D : 9 kg pour 65 €. Ici, c’est aussi la meilleure solution possible.
def sac_glouton(objets, capacite):
"""objets : liste de tuples (nom, poids, valeur)."""
def ratio(o):
return o[2] / o[1]
tries = sorted(objets, key=ratio, reverse=True)
choisis = []
poids = 0
for nom, p, v in tries:
if poids + p <= capacite:
choisis.append(nom)
poids = poids + p
return choisis4. D’autres problèmes gloutons
Planification d’activités : pour placer le plus grand nombre possible d’activités qui ne se chevauchent pas dans une salle, on choisit à chaque fois, parmi les activités compatibles, celle qui se termine le plus tôt. Pour ce problème, on peut démontrer que ce choix glouton est optimal.
À retenir
- Un algorithme glouton fait à chaque étape le choix localement optimal, sans retour en arrière.
- Rendu de monnaie : rendre la plus grande pièce possible ; optimal pour l’euro, pas pour tout système (1, 3, 4 pour 6).
- Sac à dos : on trie par rapport valeur/poids décroissant et on prend ce qui rentre ; pas toujours optimal.
- Le glouton est rapide ; la recherche exhaustive (2ⁿ cas) est sûre mais vite impraticable.
- Pour montrer qu’un glouton n’est pas optimal, il suffit d’un contre-exemple.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.