Exercices sur la programmation dynamique

Réponse B. La programmation dynamique s’applique lorsque les sous-problèmes se chevauchent : un même calcul est nécessaire à plusieurs reprises. On stocke alors les résultats pour éviter les recalculs.

• A est faux : quand les sous-problèmes sont indépendants, « diviser pour régner » suffit ;
• C est faux : il peut exister plusieurs solutions, la programmation dynamique cherche la solution optimale ;
• D est faux : la complexité dépend du problème (souvent quadratique ou pseudo-polynomiale).

Réponse C. Chaque appel engendre deux appels récursifs, et les mêmes valeurs sont recalculées un nombre exponentiel de fois. L’arbre d’appels a une profondeur $n$ et sa taille croît exponentiellement.

• A est faux : c’est la complexité de la version avec mémoïsation ou bottom-up ;
• B est faux : la croissance est bien plus rapide que quadratique ;
• D est faux : aucun mécanisme ne divise le problème par deux à chaque étape.

Réponse B. La mémoïsation conserve la structure récursive mais ajoute un dictionnaire ou un tableau pour stocker les résultats déjà calculés. Quand un sous-problème est rencontré à nouveau, on retourne directement le résultat stocké.

• A est faux : c’est l’approche ascendante (bottom-up), pas la mémoïsation ;
• C est faux : la mémoïsation n’est pas un algorithme glouton ;
• D est faux : la mémoïsation utilise la récursivité (contrairement à l’approche bottom-up).

Réponse C. La case $(i, p)$ du tableau contient la valeur maximale que l’on peut obtenir en considérant les $i$ premiers objets avec une capacité de $p$ kg.

• A est faux : les colonnes représentent le poids, pas les lignes ;
• B est faux : le tableau ne compte pas les objets d’un poids donné ;
• D est faux : on cherche la valeur maximale, pas le nombre de combinaisons.

Réponse B. L’algorithme glouton choisit d’abord la plus grande pièce possible : 4, puis il reste $6 - 4 = 2$, et il rend $1 + 1$. Total : trois pièces. Or la solution optimale est deux pièces de 3. Cet exemple montre que le système $(1, 3, 4)$ n’est pas canonique : l’algorithme glouton ne donne pas toujours le résultat optimal.

• A est faux : c’est la solution optimale, mais le glouton ne la trouve pas car il commence par la pièce de 4 ;
• C est faux : même remarque ;
• D est faux : le glouton ne choisit jamais la plus petite pièce tant qu’une plus grande convient.

Partie A.

def fibo(n):
    if n == 0 or n == 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

Arbre des appels pour fibo(5) :

                    fibo(5)
                   /       \
              fibo(4)       fibo(3)
             /     \        /     \
         fibo(3)  fibo(2) fibo(2) fibo(1)
        /    \    /    \   /    \
    fibo(2) fibo(1) fibo(1) fibo(0) fibo(1) fibo(0)
    /    \
fibo(1) fibo(0)

fibo(2) est calculé trois fois. Plus $n$ augmente, plus les recalculs explosent.

Pour fibo(35), le temps est de l’ordre de la seconde. Pour fibo(40), cela prend déjà une dizaine de secondes.

Partie B.

def fibo_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0 or n == 1:
        return n
    memo[n] = fibo_memo(n - 1, memo) + fibo_memo(n - 2, memo)
    return memo[n]

fibo_memo(100) retourne 354224848179261915075 quasi instantanément. Chaque valeur est calculée une seule fois puis stockée dans le dictionnaire.

Partie C.

def fibo_dyn(n):
    t = [0] * (n + 1)
    t[1] = 1
    for i in range(2, n + 1):
        t[i] = t[i - 1] + t[i - 2]
    return t[n]

La complexité est $O(n)$ en temps et $O(n)$ en espace (le tableau de taille $n + 1$).

On peut réduire l’espace à $O(1)$ en ne conservant que les deux dernières valeurs :

def fibo_opt(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Partie A.

def rendu_glouton(monnaie, s):
    resultat = []
    for piece in reversed(monnaie):
        while s >= piece:
            resultat.append(piece)
            s -= piece
    return resultat

Test : rendu_glouton([1, 3, 4], 6) retourne [4, 1, 1] (trois pièces). La solution optimale est [3, 3] (deux pièces). L’algorithme glouton n’est pas optimal ici.

Partie B.

3. Tableau rempli :

Pour la ligne {1, 3} : la somme 3 peut être rendue avec une seule pièce de 3, la somme 6 avec deux pièces de 3. Pour la ligne {1, 3, 4} : la somme 4 peut être rendue avec une seule pièce de 4, la somme 5 avec une pièce de 4 et une de 1.

4. Relation de récurrence : soit $T[i][j]$ le nombre minimal de pièces pour rendre la somme $j$ avec les $i$ premières pièces. Si la $i$-ème pièce a pour valeur $v_i$ :

$$T[i][j] = \min(T[i-1][j],; T[i][j - v_i] + 1) \text{ si } j \geq v_i$$

Le premier terme correspond au cas où on n’utilise pas la pièce $v_i$. Le second correspond au cas où on utilise au moins une pièce $v_i$ (et on peut en utiliser d’autres ensuite, d’où $T[i]$ et non $T[i-1]$).

5. Implémentation :

def rendu_dynamique(monnaie, s):
    n = len(monnaie)
    INF = float("inf")
    t = [[INF] * (s + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        t[i][0] = 0
    for i in range(1, n + 1):
        v = monnaie[i - 1]
        for j in range(1, s + 1):
            t[i][j] = t[i - 1][j]  # on n'utilise pas la pièce v
            if j >= v and t[i][j - v] + 1 < t[i][j]:
                t[i][j] = t[i][j - v] + 1
    return t[n][s]

print(rendu_dynamique([1, 3, 4], 6))  # 2

6. Version avec décomposition :

def rendu_dynamique_complet(monnaie, s):
    n = len(monnaie)
    INF = float("inf")
    t = [[INF] * (s + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        t[i][0] = 0
    for i in range(1, n + 1):
        v = monnaie[i - 1]
        for j in range(1, s + 1):
            t[i][j] = t[i - 1][j]
            if j >= v and t[i][j - v] + 1 < t[i][j]:
                t[i][j] = t[i][j - v] + 1

    # Reconstruction de la solution
    pieces = []
    i, j = n, s
    while j > 0:
        if i > 0 and t[i][j] == t[i - 1][j]:
            i -= 1  # on n'a pas utilisé la pièce i
        else:
            pieces.append(monnaie[i - 1])
            j -= monnaie[i - 1]
    return t[n][s], pieces

nb, decomposition = rendu_dynamique_complet([1, 3, 4], 6)
print(nb, decomposition)  # 2 [3, 3]

La complexité est $O(n \times s)$ en temps et en espace, où $n$ est le nombre de types de pièces et $s$ la somme à rendre.

1. Rapports valeur/poids : A = 5/3 ≈ 1.67, B = 8/4 = 2, C = 4/2 = 2, D = 6/1 = 6.

Tri par rapport décroissant : D (6), B (2), C (2), A (1.67). On prend D (poids 1, reste 6), B (poids 4, reste 2), C (poids 2, reste 0). Valeur totale : $6 + 8 + 4 = 18$. Poids total : 7 kg.

2. Tableau de programmation dynamique :

Explication de quelques cases :

• Case (B, 7) : $\max(T[\text{A}][7],; T[\text{A}][7-4] + 8) = \max(5,; 5 + 8) = 13$.
• Case (D, 5) : $\max(T[\text{C}][5],; T[\text{C}][5-1] + 6) = \max(9,; 8 + 6) = 14$.

3. Valeur maximale : $18$ (case en bas à droite).

Remontée : $T[\text{D}][7] = 18 \neq T[\text{C}][7] = 13$, donc D est pris (reste poids $7 - 1 = 6$). $T[\text{C}][6] = 12 \neq T[\text{B}][6] = 8$, donc C est pris (reste $6 - 2 = 4$). $T[\text{B}][4] = 8 \neq T[\text{A}][4] = 5$, donc B est pris (reste $4 - 4 = 0$). Plus de poids disponible. Objets sélectionnés : B, C, D. Valeur : $8 + 4 + 6 = 18$.

Ici, l’algorithme glouton trouvait déjà la solution optimale. Ce n’est pas toujours le cas.

4. Implémentation :

def sac_a_dos(objets, w):
    n = len(objets)
    t = [[0] * (w + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        valeur, poids = objets[i - 1]
        for p in range(w + 1):
            t[i][p] = t[i - 1][p]  # on ne prend pas l'objet i
            if p >= poids and t[i - 1][p - poids] + valeur > t[i][p]:
                t[i][p] = t[i - 1][p - poids] + valeur

    # Reconstruction de la solution
    selection = []
    p = w
    for i in range(n, 0, -1):
        if t[i][p] != t[i - 1][p]:
            selection.append(i - 1)  # indice de l'objet
            p -= objets[i - 1][1]

    return t[n][w], selection

objets = [(5, 3), (8, 4), (4, 2), (6, 1)]
valeur_max, indices = sac_a_dos(objets, 7)
print(f"Valeur maximale : {valeur_max}")
print(f"Objets sélectionnés : {indices}")

Résultat : valeur maximale 18, objets d’indices [3, 2, 1] (D, C, B).

La complexité est $O(n \times w)$ en temps et en espace, où $n$ est le nombre d’objets et $w$ la capacité du sac. C’est une complexité pseudo-polynomiale : elle dépend de la valeur de $w$ et non de la taille de son encodage.

1. Tableau pour "BAIN" et "BRIN" :

Explication de la case (A, R) = 1 : on compare "BA" et "BR". Le minimum entre :

• suppression : $d(\text{“B”}, \text{“BR”}) + 1 = 1 + 1 = 2$ ;
• insertion : $d(\text{“BA”}, \text{“B”}) + 1 = 1 + 1 = 2$ ;
• substitution : $d(\text{“B”}, \text{“B”}) + 1 = 0 + 1 = 1$ (car A ≠ R).

Résultat : $\min(2, 2, 1) = 1$.

2. La distance d’édition est 1 (case en bas à droite). L’unique opération est une substitution du A en R (transformer "BAIN" en "BRIN").

3. Implémentation :

def distance_edition(a, b):
    n, m = len(a), len(b)
    t = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        t[i][0] = i
    for j in range(m + 1):
        t[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cout = 0 if a[i - 1] == b[j - 1] else 1
            t[i][j] = min(
                t[i - 1][j] + 1,       # suppression
                t[i][j - 1] + 1,       # insertion
                t[i - 1][j - 1] + cout  # substitution (ou identité)
            )
    return t[n][m]

4. Tests :

print(distance_edition("CHAT", "CHATS"))        # 1
print(distance_edition("NICHE", "CHIEN"))        # 4
print(distance_edition("ALGORITHME", "ALTRUISME"))  # 5
print(distance_edition("BAIN", "BRIN"))          # 1

Pour "CHAT" → "CHATS" : une insertion du S à la fin. Distance = 1.

Pour "NICHE" → "CHIEN" : distance = 4 (par exemple : supprimer N, supprimer I, insérer I après CH, insérer N ; d’autres suites de quatre opérations existent).

La complexité est $O(n \times m)$ en temps et en espace, où $n$ et $m$ sont les longueurs des deux chaînes.

1. Calcul à la main :

• $f(1) = 1$ : la seule façon est (1).
• $f(2) = 2$ : soit (1, 1), soit (2).
• $f(3) = 3$ : (1, 1, 1), (1, 2), (2, 1).
• $f(4) = 5$ : (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2).
• $f(5) = 8$ : on les énumère ou on utilise la relation.

2. Pour atteindre la marche $n$, le dernier pas vient soit de la marche $n - 1$ (un pas de 1), soit de la marche $n - 2$ (un pas de 2). Donc $f(n) = f(n-1) + f(n-2)$. Avec $f(1) = 1$ et $f(2) = 2$, on reconnaît la suite de Fibonacci décalée : $f(n) = F_{n+1}$ (où $F$ est la suite de Fibonacci classique).

3. Version récursive naïve :

def montee_recursive(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return montee_recursive(n - 1) + montee_recursive(n - 2)

Pour $n = 30$, le calcul est très lent (complexité exponentielle $O(2^n)$), exactement comme pour Fibonacci.

4. Version avec mémoïsation :

def montee_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 1:
        return 1
    if n == 2:
        return 2
    memo[n] = montee_memo(n - 1, memo) + montee_memo(n - 2, memo)
    return memo[n]

5. Version bottom-up :

def montee_dyn(n):
    if n == 1:
        return 1
    t = [0] * (n + 1)
    t[1] = 1
    t[2] = 2
    for i in range(3, n + 1):
        t[i] = t[i - 1] + t[i - 2]
    return t[n]

montee_dyn(30) retourne 1346269 instantanément.

6. Extension avec coûts : la relation de récurrence est :

$$C(i) = c_i + \min(C(i-1),; C(i-2))$$

avec $C(1) = c_1$ et $C(2) = c_2$.

def cout_minimal(couts):
    n = len(couts)
    if n == 0:
        return 0
    if n == 1:
        return couts[0]
    t = [0] * n
    t[0] = couts[0]
    t[1] = couts[1]
    for i in range(2, n):
        t[i] = couts[i] + min(t[i - 1], t[i - 2])
    return t[n - 1]

# Exemple : marches de coût [2, 5, 1, 8, 3, 6]
print(cout_minimal([2, 5, 1, 8, 3, 6]))  # 12

Vérification : le chemin optimal est marche 1 (coût 2) → marche 3 (coût 1) → marche 5 (coût 3) → marche 6 (coût 6). Total : $2 + 1 + 3 + 6 = 12$. L’alternative marche 2 → marche 4 → marche 6 donne $5 + 8 + 6 = 19$, ce qui est plus coûteux.

Ce problème de la montée d’escalier avec coûts est un classique de la programmation dynamique qui montre comment adapter la récurrence de Fibonacci pour résoudre un problème d’optimisation.