19 - Algorithmes gloutons
Exercice 0 : QCM – vérification des prérequis
Pour chaque question, une seule réponse est correcte.
1. Quel est le principe d’un algorithme glouton ?
- A. Il explore toutes les solutions possibles pour trouver la meilleure
- B. Il fait à chaque étape le choix localement optimal, sans revenir en arrière
- C. Il divise le problème en sous-problèmes indépendants
- D. Il trie d’abord les données puis applique une recherche dichotomique
Correction
Réponse : B. Un algorithme glouton (greedy) construit une solution étape par étape, en faisant à chaque fois le choix qui semble le meilleur sur le moment, sans remettre en question les choix précédents.
- A est faux : explorer toutes les solutions est une approche par force brute (ou backtracking).
- C est faux : c’est le principe du « diviser pour régner ».
- D est faux : cela décrit une recherche dichotomique, pas un algorithme glouton.
2. Un algorithme glouton donne-t-il toujours la solution optimale ?
- A. Oui, toujours
- B. Non, jamais
- C. Cela dépend du problème
- D. Seulement si les données sont triées
Correction
Réponse : C. Pour certains problèmes (comme le rendu de monnaie avec le système euro), le glouton donne la solution optimale. Pour d’autres (comme le sac à dos entier), il peut donner une solution sous-optimale.
- A est faux : le contre-exemple classique est le sac à dos 0/1.
- B est faux : il existe des problèmes pour lesquels le glouton est optimal.
- D est faux : le tri est souvent une étape du glouton, mais ne garantit pas l’optimalité.
3. Pour rendre 8 centimes avec les pièces [6, 4, 1], l’algorithme glouton choisit d’abord la pièce de 6. Combien de pièces utilise-t-il au total ?
- A. 2 pièces (6, 4)
- B. 3 pièces (6, 1, 1)
- C. 2 pièces (4, 4)
- D. 4 pièces (1, 1, 1, 1, 1, 1, 1, 1)
Correction
Réponse : B. L’algorithme glouton prend d’abord la plus grande pièce possible : 6 (reste 2), puis 1 (reste 1), puis 1 (reste 0). Total : trois pièces.
- C est faux : c’est la solution optimale (deux pièces de 4), mais le glouton ne la trouve pas car il choisit d’abord 6.
- D est faux : le glouton ne se limite pas aux pièces de 1.
C’est un exemple classique où le glouton ne donne pas la solution optimale.
Exemple travaillé : rendu de monnaie glouton
Problème : rendre 678 centimes avec le système euro [200, 100, 50, 20, 10, 5, 2, 1].
Principe glouton : à chaque étape, choisir la plus grande pièce possible sans dépasser le montant restant.
Trace :
| Étape | Montant restant | Plus grande pièce ≤ restant | Choix |
|---|---|---|---|
| 1 | 678 | 200 | 200 |
| 2 | 478 | 200 | 200 |
| 3 | 278 | 200 | 200 |
| 4 | 78 | 50 | 50 |
| 5 | 28 | 20 | 20 |
| 6 | 8 | 5 | 5 |
| 7 | 3 | 2 | 2 |
| 8 | 1 | 1 | 1 |
Résultat : [200, 200, 200, 50, 20, 5, 2, 1] → huit pièces.
Algorithme :
def rendu_monnaie(montant, pieces):
"""Renvoie la liste des pièces pour rendre montant centimes."""
resultat = []
for p in pieces: # pièces triées par valeur décroissante
while montant >= p:
resultat.append(p)
montant -= p
return resultat
Exercice 1 : rendu de monnaie
- Programmer la fonction
rendu_monnaie(montant, pieces)qui renvoie la liste des pièces utilisées. - Tester avec le système
[200, 100, 50, 20, 10, 5, 2, 1]pour rendre 678 centimes. - Tester avec le système
[6, 4, 1]pour rendre 8 centimes. Comparer le résultat glouton avec la solution optimale.
Correction
def rendu_monnaie(montant, pieces):
"""Renvoie la liste des pièces utilisées (glouton)."""
resultat = []
for p in pieces:
while montant >= p:
resultat.append(p)
montant -= p
return resultat
# Test 1 : système euro
print(rendu_monnaie(678, [200, 100, 50, 20, 10, 5, 2, 1]))
# [200, 200, 200, 50, 20, 5, 2, 1]
# Test 2 : système pathologique
print(rendu_monnaie(8, [6, 4, 1]))
# [6, 1, 1] → 3 pièces (le glouton)
# Solution optimale : [4, 4] → 2 pièces
Avec le système euro, le glouton donne toujours la solution optimale. Avec [6, 4, 1], il utilise trois pièces au lieu de deux : la stratégie gloutonne n’est pas toujours optimale.
Exercice 2 : nombre de pièces
Modifier la fonction rendu_monnaie pour qu’elle renvoie un dictionnaire associant chaque valeur de pièce utilisée à son nombre d’occurrences. Par exemple, pour 678 centimes :
{200: 3, 50: 1, 20: 1, 5: 1, 2: 1, 1: 1}
Correction
def rendu_monnaie_dico(montant, pieces):
"""Renvoie un dictionnaire {valeur_pièce: nombre}."""
resultat = {}
for p in pieces:
count = 0
while montant >= p:
count += 1
montant -= p
if count > 0:
resultat[p] = count
return resultat
print(rendu_monnaie_dico(678, [200, 100, 50, 20, 10, 5, 2, 1]))
# {200: 3, 50: 1, 20: 1, 5: 1, 2: 1, 1: 1}
Variante : on peut aussi utiliser montant // p pour calculer directement le nombre de pièces de chaque valeur.
def rendu_monnaie_dico_v2(montant, pieces):
resultat = {}
for p in pieces:
nb = montant // p
if nb > 0:
resultat[p] = nb
montant -= nb * p
return resultat
Exercice 3 : sac à dos fractionnaire
On dispose d’objets ayant chacun un poids et une valeur. On veut remplir un sac de capacité limitée en maximisant la valeur totale. Dans le cas fractionnaire, on peut prendre une fraction d’un objet.
Objets disponibles :
| Objet | A | B | C | D |
|---|---|---|---|---|
| Poids (kg) | 3 | 4 | 5 | 6 |
| Valeur (€) | 9 | 10 | 15 | 12 |
| Ratio (€/kg) | 3,0 | 2,5 | 3,0 | 2,0 |
- Programmer la fonction
sac_a_dos_frac(poids_max, objets)oùobjetsest une liste de tuples(poids, valeur). - Tester avec un sac de 10 kg.
- Déterminer la complexité temporelle de cette fonction.
Correction
def sac_a_dos_frac(poids_max, objets):
"""Sac à dos fractionnaire (glouton par ratio valeur/poids)."""
# Trier par ratio décroissant
tries = sorted(objets, key=lambda o: o[1] / o[0], reverse=True)
valeur_totale = 0
poids_restant = poids_max
contenu = []
for poids, valeur in tries:
if poids_restant <= 0:
break
if poids <= poids_restant:
contenu.append((poids, valeur, 1.0))
valeur_totale += valeur
poids_restant -= poids
else:
fraction = poids_restant / poids
contenu.append((poids, valeur, round(fraction, 2)))
valeur_totale += valeur * fraction
poids_restant = 0
return round(valeur_totale, 2), contenu
objets = [(3, 9), (4, 10), (5, 15), (6, 12)]
valeur, contenu = sac_a_dos_frac(10, objets)
print(f"Valeur totale : {valeur} €")
for p, v, f in contenu:
print(f" Objet ({p}kg, {v}€) : {f*100:.0f}%")
Complexité : le tri coûte $O(n \log n)$, le parcours coûte $O(n)$. La complexité totale est $O(n \log n)$.
Exercice 4 : comparaison de stratégies
Pour le problème du sac à dos (entier, sans fraction) avec les données de l’exercice 3, programmer et comparer les trois stratégies gloutonnes (tri par valeur décroissante, tri par poids croissant, tri par ratio décroissant). Afficher le contenu du sac et la valeur totale pour chacune.
Correction
def sac_glouton(poids_max, objets, cle_tri):
"""Sac à dos entier avec stratégie gloutonne selon cle_tri."""
tries = sorted(objets, key=cle_tri)
valeur_totale = 0
poids_restant = poids_max
contenu = []
for poids, valeur in tries:
if poids <= poids_restant:
contenu.append((poids, valeur))
valeur_totale += valeur
poids_restant -= poids
return valeur_totale, contenu
objets = [(3, 9), (4, 10), (5, 15), (6, 12)]
# Tri par valeur décroissante
v1, c1 = sac_glouton(10, objets, lambda o: -o[1])
print(f"Par valeur : {v1}€, {c1}")
# Tri par poids croissant
v2, c2 = sac_glouton(10, objets, lambda o: o[0])
print(f"Par poids : {v2}€, {c2}")
# Tri par ratio décroissant
v3, c3 = sac_glouton(10, objets, lambda o: -o[1]/o[0])
print(f"Par ratio : {v3}€, {c3}")
Les trois stratégies donnent des résultats différents. Aucune ne garantit l’optimalité pour le sac à dos entier.
Exercice 5 : limites du glouton
Considérons les objets suivants et un sac de 4 kg :
| Objet | A | B | C |
|---|---|---|---|
| Valeur | 165 | 100 | 100 |
| Poids | 3 | 2 | 2 |
- Appliquer l’algorithme glouton (tri par ratio). Quel résultat obtient-on ?
- Trouver « à la main » une meilleure solution.
- Expliquer pourquoi l’algorithme glouton échoue dans ce cas.
Correction
1. Ratios : A = 165/3 = 55, B = 100/2 = 50, C = 100/2 = 50. Le glouton prend A (3 kg, 165 €). Il reste 1 kg : ni B ni C ne rentrent. Valeur totale : 165 €.
2. En prenant B et C : poids = 2 + 2 = 4 kg, valeur = 100 + 100 = 200 €. C’est mieux.
3. Le glouton échoue car il fait un choix irréversible : en prenant l’objet A (qui a le meilleur ratio), il gaspille 1 kg de capacité. Les objets B et C, moins « rentables » individuellement, remplissent exactement le sac et totalisent une valeur supérieure. Le glouton ne peut pas « revenir en arrière » pour corriger son premier choix.
Exercice 6 : planification d’activités
Un élève dispose d’une journée et souhaite participer au maximum d’activités. Chaque activité a une heure de début et une heure de fin, et deux activités ne peuvent se chevaucher.
| Activité | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Début | 8 | 9 | 10 | 11 | 13 | 14 |
| Fin | 10 | 12 | 11 | 14 | 15 | 16 |
- Proposer une stratégie gloutonne pour maximiser le nombre d’activités.
- Appliquer cette stratégie aux données ci-dessus.
- Programmer cette stratégie en Python.
Indication : trier les activités par heure de fin croissante et sélectionner chaque activité dont l’heure de début est postérieure ou égale à la fin de la dernière activité choisie.
Correction
1. La stratégie gloutonne consiste à toujours choisir l’activité qui se termine le plus tôt (parmi celles compatibles). Cela laisse le maximum de temps pour les activités suivantes.
2. Activités triées par fin : A(8-10), C(10-11), B(9-12), D(11-14), E(13-15), F(14-16).
- On prend A (fin à 10).
- C commence à 10 ≥ 10 : on prend C (fin à 11).
- B commence à 9 < 11 : incompatible.
- D commence à 11 ≥ 11 : on prend D (fin à 14).
- E commence à 13 < 14 : incompatible.
- F commence à 14 ≥ 14 : on prend F (fin à 16).
Résultat : A, C, D, F → quatre activités.
3.
def planification(activites):
"""Sélection d'activités par fin la plus précoce."""
# Trier par heure de fin
triees = sorted(activites, key=lambda a: a[2])
selection = [triees[0]]
for i in range(1, len(triees)):
nom, debut, fin = triees[i]
if debut >= selection[-1][2]:
selection.append(triees[i])
return selection
activites = [
("A", 8, 10), ("B", 9, 12), ("C", 10, 11),
("D", 11, 14), ("E", 13, 15), ("F", 14, 16),
]
resultat = planification(activites)
for nom, debut, fin in resultat:
print(f"{nom} : {debut}h - {fin}h")
Remarque : pour ce problème, la stratégie gloutonne « fin la plus précoce » donne toujours la solution optimale. C’est un résultat classique d’algorithmique.