Algorithmes gloutons : 12 exercices corrigés

Corrigé

reste 3 275 : plus grosse coupure qui tient = 2 000  ->  reste 1 275
reste 1 275 : 1 000                                 ->  reste   275
reste   275 : 100                                   ->  reste   175
reste   175 : 100                                   ->  reste    75
reste    75 : 50                                    ->  reste    25
reste    25 : 25                                    ->  reste     0

1 billet de 2 000, 1 billet de 1 000, 2 pièces de 100, 1 pièce de 50 et 1 pièce de 25, soit 6 coupures.

On vérifie : 2 000 + 1 000 + 100 + 100 + 50 + 25 = 3 275. ✓

Et c'est bien le minimum : le franc CFA est un système canonique.

Corrigé

Glouton :

reste 12 : on prend 10  ->  reste 2
reste  2 : on prend 1   ->  reste 1
reste  1 : on prend 1   ->  reste 0

3 coupures : 10 + 1 + 1

Optimum : 6 + 6 = 2 coupures.

Le glouton fait donc 50 % de trop. Il s'est fait avoir en prenant le 10, qui laisse un reste de 2 que seules les pièces de 1 peuvent couvrir.

La leçon : un système où une grosse coupure n'est pas un multiple « confortable » des plus petites casse le glouton. Ici 10 n'est ni un multiple de 6, ni assez proche de 12 pour que ça tombe juste.

Corrigé

COUPURES = [1, 2, 5, 10, 25, 50, 100, 500, 1000, 2000, 5000, 10000]


def rendre(montant, coupures=COUPURES):
    # renvoie la liste des coupures, ou None si le rendu echoue
    reste = montant
    rendu = []

    for piece in sorted(coupures, reverse=True):
        while reste >= piece:
            rendu.append(piece)
            reste -= piece

    return rendu if reste == 0 else None

>>> rendre(3275)
[2000, 1000, 100, 100, 50, 25]

>>> rendre(7, [2, 5])
None

Deux détails qui comptent :

• Le sorted(..., reverse=True) garantit qu'on commence par la plus grosse, même si la liste fournie est en désordre.
• Le while intérieur prend toutes les coupures d'une valeur donnée d'un coup. Un simple if n'en prendrait qu'une, et il faudrait reparcourir la liste.

On peut remplacer le while par une division entière : nombre = reste // piece, ce qui est plus rapide.

Corrigé

Glouton avec stock :

reste 1 400 : 1 000 (il en reste 1)  ->  reste 400
reste   400 : 100 x 3 disponibles    ->  reste 100
reste   100 : plus de pieces de 100
              pieces de 25 : 4 x 25 = 100  ->  reste 0

Oui : 1 000 + 3×100 + 4×25 = 1 400. Elle utilise toute sa caisse, soit 8 coupures.

Mais attention. Le glouton a vidé la caisse. S'il était possible de rendre autrement, il vaudrait peut-être mieux garder de la monnaie pour la cliente suivante.

Ici il n'y avait pas le choix : le total de la caisse vaut exactement 1 400 FCFA. Mais l'exercice montre la limite du critère « le moins de coupures » : quand la caisse est serrée, le vrai objectif devient « préserver le fonds de caisse », et ce n'est pas le même problème.

Corrigé

Densités :

Vanille : 45 000 / 3  = 15 000 FCFA/kg
Poivre  : 80 000 / 8  = 10 000 FCFA/kg
Cafe    : 98 000 / 14 =  7 000 FCFA/kg
Ndole   : 30 000 / 6  =  5 000 FCFA/kg

Glouton :

vanille 3 kg   ->  3 kg,  45 000     reste 17 kg
poivre  8 kg   -> 11 kg, 125 000     reste  9 kg
cafe   14 kg   -> ne rentre pas
ndole   6 kg   -> 17 kg, 155 000     reste  3 kg

total : 17 kg, 155 000 FCFA

Optimum : vanille + poivre + ndolé = 17 kg pour 155 000 FCFA. Testons les autres combinaisons tenant dans 20 kg :

vanille + cafe        : 17 kg, 143 000
poivre  + cafe        : 22 kg, dépasse
vanille + poivre + ndole : 17 kg, 155 000   <-- le meilleur
cafe + ndole          : 20 kg, 128 000

Ici le glouton trouve l'optimum : 155 000 FCFA.

Cela n'en fait pas un algorithme correct pour autant. Il a eu raison sur ce jeu de données, c'est tout. Le chapitre 3 du cours montre un jeu très proche où il perd 10 000 FCFA.

Corrigé

Le mécanisme à reproduire : un petit objet très dense qui fait rater un gros objet qui remplirait mieux.

Capacité : 10 kg.

GLOUTON :
  safou 1 kg  ->  1 kg,  12 000    reste 9 kg
  miel  5 kg  ->  6 kg,  62 000    reste 4 kg
  cacao 5 kg  -> ne rentre pas
  total : 6 kg, 62 000 FCFA

OPTIMUM :
  miel + cacao = 10 kg, 95 000 FCFA

Le glouton perd 33 000 FCFA, soit 35 % de l'optimum.

Pourquoi : le safou ne pèse qu'un kilo mais il casse la parité. Sans lui, deux lots de 5 kg remplissent exactement le car. Avec lui, il reste 4 kg inutilisables.

C'est la recette générale d'un contre-exemple : faire en sorte que le choix glouton laisse un reste inexploitable.

Corrigé

safou 1 kg entier     -> 12 000        reste 9 kg
miel  5 kg entiers    -> 50 000        reste 4 kg
cacao 4 kg sur 5      -> 45 000 x 4/5
                      = 36 000        reste 0 kg

total : 10 kg, 98 000 FCFA

98 000 FCFA, contre 95 000 pour le meilleur chargement en lots entiers.

Deux observations :

• Le résultat dépasse l'optimum entier. C'est normal : autoriser les coupes ne peut qu'améliorer, puisque toute solution entière reste permise.
• Une seule marchandise est coupée, la dernière. C'est une propriété générale du sac fractionnaire.

Et cette fois le résultat est garanti optimal : la preuve par échange du chapitre 4 s'applique.

Corrigé

def charger(marchandises, capacite):
    # les lots sont divisibles : on paie au prorata du poids pris
    par_densite = sorted(marchandises,
                         key=lambda m: m[2] / m[1],
                         reverse=True)

    reste = capacite
    valeur = 0.0
    chargement = []

    for nom, poids, prix in par_densite:
        if reste <= 0:
            break
        pris = min(poids, reste)
        valeur += prix * pris / poids
        chargement.append((nom, pris))
        reste -= pris

    return valeur, chargement

>>> charger([("Safou",1,12000),("Miel",5,50000),("Cacao",5,45000)], 10)
(98000.0, [('Safou', 1), ('Miel', 5), ('Cacao', 4)])

Le min(poids, reste) est tout l'algorithme : il prend le lot entier s'il tient, sinon juste ce qui reste de place.

Complexité : O(n log n), dominée par le tri. Le parcours est linéaire.

Attention au piège : si l'on retire le break, l'algorithme continue de parcourir les marchandises avec reste = 0. Le min renvoie alors 0 et on ajoute des lots de zéro kilo au chargement : inoffensif mais sale.

Corrigé

Tri par heure de fin : B(10), C(11), A(12), D(14), E(15), G(16), F(18).

salle libre a 0

B  9h-10h : 9  >= 0   -> PRIS    libre a 10h
C 10h-11h : 10 >= 10  -> PRIS    libre a 11h
A  8h-12h : 8  < 11   -> refuse
D 11h-14h : 11 >= 11  -> PRIS    libre a 14h
E 13h-15h : 13 < 14   -> refuse
G 15h-16h : 15 >= 14  -> PRIS    libre a 16h
F 14h-18h : 14 < 16   -> refuse

B, C, D, G : soit 4 activités, et c'est le maximum.

Remarquez que l'activité A, la plus longue et la plus matinale, est refusée : elle bloquerait la salle de 8 h à 12 h pour une seule réservation, là où B et C en logent deux.

Corrigé

Durées : B = 1 h, C = 1 h, G = 1 h, E = 2 h, D = 3 h, A = 4 h, F = 4 h.

B  9h-10h (1h) -> PRIS
C 10h-11h (1h) -> PRIS    (ne chevauche pas B)
G 15h-16h (1h) -> PRIS
E 13h-15h (2h) -> PRIS    (ne chevauche ni C ni G)
D 11h-14h (3h) -> chevauche E -> refuse
A  8h-12h (4h) -> chevauche B -> refuse
F 14h-18h (4h) -> chevauche G -> refuse

B, C, E, G : soit 4 activités. Ici, le critère marche aussi.

Mais c'est une coïncidence. Voici un cas où il s'effondre :

Tontine  8h - 13h   (5h)
Point    12h - 14h  (2h)   <-- la plus courte
Chorale  13h - 18h  (5h)

Le critère « le plus court » prend le point du chef : ses deux heures mordent à la fois sur la tontine et sur la chorale. 1 seule activité, alors que le critère « heure de fin » en obtient 2.

Un critère qui réussit sur vos données d'essai n'est pas démontré pour autant.

Corrigé

def planifier(demandes):
    # critere glouton : l'activite qui libere la salle le plus tot
    par_fin = sorted(demandes, key=lambda d: d[2])

    retenues = []
    libre_a = 0

    for nom, debut, fin in par_fin:
        if debut >= libre_a:
            retenues.append((nom, debut, fin))
            libre_a = fin

    return retenues

>>> demandes = [("A",8,12),("B",9,10),("C",10,11),("D",11,14),
...             ("E",13,15),("F",14,18),("G",15,16)]
>>> [a[0] for a in planifier(demandes)]
['B', 'C', 'D', 'G']

Trois détails :

• libre_a = 0 suppose que les horaires sont positifs. Avec des dates quelconques, initialisez à float("-inf").
• Le test est >= et non > : une activité peut commencer à l'heure exacte où la précédente finit.
• Une seule variable suffit pour tout l'état. C'est la signature d'un glouton : aucune mémoire des choix passés n'est nécessaire.

Complexité : O(n log n) pour le tri, O(n) pour le parcours.

Corrigé

Soit G = (g₁, …, g_p) la solution du glouton et O = (o₁, …, o_q) une solution optimale, toutes deux rangées par date de fin. On montre que p = q.

1. L'échange de la première activité.

Par construction, g₁ est celle qui finit le plus tôt parmi toutes les demandes. Donc :

fin(g₁) ≤ fin(o₁)

Remplaçons o₁ par g₁ dans O. Est-ce encore valide ? L'activité o₂ commençait après fin(o₁) ; comme fin(g₁) ≤ fin(o₁), elle commence aussi après fin(g₁). Aucun chevauchement n'apparaît.

La solution obtenue a toujours q activités : elle est encore optimale.

2. Récurrence.

Une fois g₁ fixée, le problème restant est le même, posé sur les demandes qui commencent après fin(g₁). Le glouton y choisit encore celle qui finit le plus tôt : le même échange s'applique à g₂, puis à g₃, et ainsi de suite.

Après p échanges, on a transformé O en une solution qui commence par g₁, …, g_p et compte toujours q activités.

3. Conclusion.

Reste-t-il des activités dans cette solution après g_p ? Une telle activité commencerait après fin(g_p), et le glouton l'aurait alors prise, puisqu'il parcourt toutes les demandes. Or il s'est arrêté à g_p.

Il n'en reste donc aucune : q = p, et le glouton est optimal. ∎

Ce qu'il faut retenir de la méthode : on ne prouve jamais directement que le glouton est le meilleur. On prouve qu'une solution optimale peut toujours être transformée en la solution gloutonne sans perdre de valeur. C'est le canevas de toutes les preuves d'optimalité d'algorithmes gloutons.