Programmation dynamique : mémoriser pour ne pas recalculer

Rendu de monnaie optimal. Avec des pièces de valeurs données (en quantité illimitée), quel est le nombre minimal de pièces pour obtenir une somme s ? Si l'on utilise d'abord une pièce p, il reste à obtenir s − p de façon optimale. D'où une solution récursive : essayer chaque pièce, et garder le meilleur résultat.

appels = 0

def nb_min_naif(s, pieces):
    global appels
    appels = appels + 1
    if s == 0:
        return 0
    meilleur = s
    for p in pieces:
        if p <= s:
            meilleur = min(meilleur, 1 + nb_min_naif(s - p, pieces))
    return meilleur

print(nb_min_naif(30, [1, 3, 4]), appels)

8 2550408

La ligne global appels (hors programme) permet seulement à la fonction de modifier la variable appels créée en dehors d'elle : on s'en sert ici pour compter les appels. Partir de meilleur = s est possible parce que la pièce de 1 fait partie du système : s pièces de 1 donnent toujours la somme s.

La réponse (8 pièces) est juste, mais il a fallu plus de deux millions et demi d'appels : les mêmes sous-problèmes (la somme 20, la somme 10…) sont recalculés un très grand nombre de fois, parce que les sous-problèmes se chevauchent.

La programmation dynamique calcule chaque sous-problème une seule fois et mémorise son résultat.

De haut en bas, avec mémoïsation. On garde la récursion, mais on range chaque résultat dans un dictionnaire memo ; avant de calculer, on regarde s'il y est déjà. Le compteur appels fonctionne comme ci-dessus.

appels = 0

def nb_min_memo(s, pieces, memo):
    global appels
    appels = appels + 1
    if s == 0:
        return 0
    if s in memo:
        return memo[s]
    meilleur = s
    for p in pieces:
        if p <= s:
            meilleur = min(meilleur, 1 + nb_min_memo(s - p, pieces, memo))
    memo[s] = meilleur
    return meilleur

print(nb_min_memo(30, [1, 3, 4], {}), appels)

8 86

Même réponse, avec 86 appels au lieu de 2 550 408.

De bas en haut, en remplissant un tableau. t[x] contient le nombre minimal de pièces pour la somme x. On remplit t de gauche à droite : t[0] = 0, et chaque case utilise des cases déjà calculées, t[x] = 1 + le plus petit des t[x − p], pour les pièces p ⩽ x.

def nb_min(s, pieces):
    t = [0]
    for x in range(1, s + 1):
        meilleur = x
        for p in pieces:
            if p <= x and t[x - p] + 1 < meilleur:
                meilleur = t[x - p] + 1
        t.append(meilleur)
    return t[s]

print(nb_min(8, [1, 4, 5]))

2

Pour 8 avec des pièces de 1, 4 et 5, l'algorithme glouton donne 5 + 1 + 1 + 1 (4 pièces) ; la programmation dynamique trouve 4 + 4 (2 pièces).

Le prix à payer est la mémoire : un tableau (ou un dictionnaire) de taille s + 1. La même idée sert pour d'autres problèmes, comme l'alignement de séquences (comparer deux mots ou deux brins d'ADN).

Énoncé. Quel nombre ce programme affiche-t-il ?

def nb_min(s, pieces):
    t = [0]
    for x in range(1, s + 1):
        meilleur = x
        for p in pieces:
            if p <= x and t[x - p] + 1 < meilleur:
                meilleur = t[x - p] + 1
        t.append(meilleur)
    return t[s]
print(nb_min(13, [1, 4, 5]))

Méthode : remplir le tableau à la main.

1. De 1 à 3, seule la pièce de 1 convient : t[x] = x.
2. t[4] = 1 + t[0] = 1 (une pièce de 4) ; t[5] = 1 + t[0] = 1 (une pièce de 5).
3. t[6] = 1 + t[5] = 2 ; t[7] = 3 ; t[8] = 1 + t[4] = 2 ; t[9] = 1 + t[5] = 2 ; t[10] = 1 + t[5] = 2 ; t[11] = 3 ; t[12] = 1 + t[8] = 3.
4. t[13] : avec 1, 1 + t[12] = 4 ; avec 4, 1 + t[9] = 3 ; avec 5, 1 + t[8] = 3. Le minimum est 3 : 5 + 4 + 4.

3

Le glouton aurait pris 5, 5, puis trois pièces de 1 : 5 pièces.