Exercices — Les algorithmes gloutons

Pr. EL HADIQ Zouhair

6 exercices Python progressifs : rendu de monnaie, contre-exemples d'optimalité, sac à dos fractionnaire, sélection d'activités et coût de Huffman. Solution modèle et complexité données pour chacun.

Conseil. Cherchez la solution seul(e) avant de comparer. Pour chaque problème, demandez-vous si le glouton est optimal ou si l'on peut exhiber un contre-exemple.

Écrire rendu_monnaie(systeme, S) où systeme est trié par ordre décroissant ; renvoie la liste des pièces rendues pour la somme S.

rendu_monnaie([50, 20, 10, 5, 2, 1], 68) → [50, 10, 5, 2, 1]
rendu_monnaie([2, 1], 5)                 → [2, 2, 1]

Solution :

def rendu_monnaie(systeme, S):
    rendu = []
    for piece in systeme:
        while S >= piece:
            rendu.append(piece)
            S = S - piece
    return rendu

Complexité : O(nombre de pièces rendues) ; avec division entière, O(taille du système).

Écrire nb_pieces(systeme, S) qui renvoie le nombre de pièces rendues par le glouton, sans construire la liste.

nb_pieces([50, 20, 10, 5, 2, 1], 68) → 5
nb_pieces([1], 7)                    → 7

Solution :

def nb_pieces(systeme, S):
    n = 0
    for piece in systeme:
        n = n + S // piece
        S = S % piece
    return n

Complexité : O(taille du système) grâce à la division entière.

Avec opt(systeme, S) (programmation dynamique, fournie) renvoyant le nombre minimal de pièces, écrire glouton_est_optimal(systeme, S) comparant le glouton à l'optimum.

glouton_est_optimal([4, 3, 1], 6) → False   # glouton 4+1+1, optimal 3+3
glouton_est_optimal([5, 2, 1], 6) → True

Solution :

def opt(systeme, S):
    INF = float('inf')
    dp = [0] + [INF] * S
    for m in range(1, S + 1):
        for p in systeme:
            if p <= m and dp[m - p] + 1 < dp[m]:
                dp[m] = dp[m - p] + 1
    return dp[S]

def glouton_est_optimal(systeme, S):
    return nb_pieces(systeme, S) == opt(systeme, S)

Idée clé : le système (1, 3, 4) n'est pas canonique → le glouton n'est pas optimal pour S = 6.

Écrire sac_fractionnaire(objets, C) (objets = liste de (valeur, poids)) renvoyant la valeur maximale transportable, arrondie à 2 décimales.

sac_fractionnaire([(60,10),(100,20),(120,30)], 50) → 240.0
sac_fractionnaire([(60,10),(100,20),(120,30)], 25) → 135.0

Solution :

def sac_fractionnaire(objets, C):
    objets = sorted(objets, key=lambda o: o[0] / o[1], reverse=True)
    valeur = 0.0
    for v, p in objets:
        if C >= p:
            valeur += v; C -= p
        else:
            valeur += v * (C / p); C = 0; break
    return round(valeur, 2)

Complexité : dominée par le tri, O(n log n). Le glouton est ici optimal.

Écrire selection_activites(activites) (activites = liste de (debut, fin)) renvoyant le nombre maximal d'activités compatibles. Glouton : trier par heure de fin croissante.

selection_activites([(1,3),(2,5),(4,7),(1,8),(5,9),(8,10)]) → 3

Solution :

def selection_activites(activites):
    activites = sorted(activites, key=lambda a: a[1])
    fin = float('-inf')
    n = 0
    for debut, f in activites:
        if debut >= fin:
            n += 1
            fin = f
    return n

Complexité : tri en O(n log n). Glouton optimal (preuve par échange sur l'heure de fin).

Écrire cout_huffman(freqs) renvoyant le coût total (somme des fusions) avec le module heapq.

cout_huffman([5, 2, 1, 1]) → 15
cout_huffman([1, 1, 1, 1]) → 8

Solution :

import heapq

def cout_huffman(freqs):
    if len(freqs) <= 1:
        return 0
    tas = list(freqs)
    heapq.heapify(tas)
    cout = 0
    while len(tas) > 1:
        a = heapq.heappop(tas)
        b = heapq.heappop(tas)
        cout += a + b
        heapq.heappush(tas, a + b)
    return cout

Complexité : O(n log n) (n−1 fusions, chacune O(log n) sur le tas). Glouton optimal.