backend / algorithmes-structures-donnees
Programmation dynamique avancée : knapsack et LCS
Explication
Ce que vous allez apprendre
- Étendre la programmation dynamique à deux dimensions quand la décision dépend de deux paramètres
- Poser et résoudre le problème du sac à dos 0/1 en formulant la récurrence "prendre ou laisser"
- Construire la table de la plus longue sous-séquence commune (LCS) entre deux chaînes
- Distinguer "calculer la valeur optimale" de "reconstruire la solution effective" à partir de la table
- Reconnaître qu'un problème est un "sac à dos" ou une "comparaison de séquences" déguisé sous un énoncé différent
Dans quel contexte ?
Un algorithme de diff, comme celui utilisé par git diff, doit afficher les lignes ajoutées et supprimées entre deux versions d'un fichier, en minimisant le nombre de changements affichés. Ce problème se ramène exactement à la plus longue sous-séquence commune (LCS) entre les deux versions : les lignes de la LCS restent inchangées à l'écran, tout le reste est marqué comme ajouté ou supprimé. C'est ce même principe de table 2D qui permet à Git de produire un diff lisible même sur des fichiers de plusieurs milliers de lignes.
D'abord, une limite de la leçon précédente
Les exemples précédents ne dépendaient que d'un seul paramètre, comme n dans Fibonacci. De nombreux problèmes réels ont deux dimensions de décision simultanées, et la table de programmation dynamique doit alors devenir une grille 2D plutôt qu'une simple liste.
Prérequis
Cette leçon suppose acquis les principes de mémoïsation et de tabulation de la leçon précédente : ici, on les applique simplement sur une grille à deux dimensions plutôt qu'une liste à une dimension.
Étape 1 : poser le problème du sac à dos 0/1
Face à des objets ayant chacun un poids et une valeur, et une capacité maximale, quel sous-ensemble maximise la valeur totale sans dépasser la capacité ?
Étape 2 : le raisonnement clé, deux choix par objet
Pour chaque objet, il n'existe que deux options mutuellement exclusives : le laisser de côté (la meilleure valeur reste celle obtenue avec les objets précédents et la même capacité), ou le prendre, à condition que son poids tienne dans la capacité restante.
Comment cela se traduit dans la table
La table table[i][c] capture "la meilleure valeur possible avec les i premiers objets et une capacité c". Chaque case se déduit uniquement de cases déjà calculées, exactement comme dans la leçon précédente, mais sur deux dimensions au lieu d'une.
| Problème | Dimensions de la table | Question posée à chaque case |
|---|---|---|
| Sac à dos 0/1 | Objets × capacité | Prendre l'objet i ou pas, dans la capacité c restante ? |
| LCS | Préfixes de la chaîne A × préfixes de la chaîne B | Les caractères courants correspondent-ils ? |
Étape 3 : un autre problème à deux dimensions, comparer deux séquences
La plus longue sous-séquence commune (LCS) et la distance d'édition partagent un schéma identique : une table indexée par les préfixes des deux chaînes comparées.
Le raisonnement à chaque case de cette table
À chaque case (i, j), on se demande si les caractères a[i-1] et b[j-1] correspondent. Si oui, on étend la solution du sous-problème diagonal ; sinon, on prend le meilleur des sous-problèmes voisins.
Piège fréquent
La table de programmation dynamique donne la VALEUR optimale (le score maximal, la longueur de la LCS...), mais pas automatiquement la solution elle-même. Pour reconstruire le sous-ensemble d'objets choisis ou la sous-séquence commune, il faut remonter la table à rebours en retraçant les décisions prises à chaque case.
Un dernier point important : reconstruire, pas seulement compter
Beaucoup de tables de PD ne donnent qu'une VALEUR optimale. Pour retrouver la solution concrète (quels objets, quelle sous-séquence), il faut remonter la table depuis la case finale, en identifiant à chaque étape quel choix a produit ce résultat.
Vers la suite
La PD explore systématiquement toutes les possibilités pour garantir l'optimum. La prochaine leçon présente une approche plus rapide mais plus risquée : les algorithmes gloutons, qui ne reviennent jamais sur un choix déjà fait.
Commandes & code
Programmation dynamique avancée : knapsack et LCS
# --- Sac à dos 0/1 (0/1 Knapsack) : chaque objet est pris entièrement ou pas du tout ---
def sac_a_dos_01(poids: list[int], valeurs: list[int], capacite: int) -> int:
# table[i][c] = valeur maximale atteignable avec les i premiers objets et une capacité c
n = len(poids)
table = [[0] * (capacite + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for c in range(capacite + 1):
# option 1 : ne pas prendre l'objet i-1
table[i][c] = table[i - 1][c]
# option 2 : le prendre, si son poids le permet
if poids[i - 1] <= c:
table[i][c] = max(table[i][c], table[i - 1][c - poids[i - 1]] + valeurs[i - 1])
return table[n][capacite] # O(n * capacite) temps et espace
assert sac_a_dos_01([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9 # objets de poids 3+4, valeur 4+5
def sac_a_dos_01_espace_optimise(poids: list[int], valeurs: list[int], capacite: int) -> int:
# O(capacite) espace : on ne garde qu'UNE ligne, parcourue à L'ENVERS pour éviter de réutiliser un objet 2 fois
table = [0] * (capacite + 1)
for i in range(len(poids)):
for c in range(capacite, poids[i] - 1, -1): # sens décroissant, crucial ici
table[c] = max(table[c], table[c - poids[i]] + valeurs[i])
return table[capacite]
assert sac_a_dos_01_espace_optimise([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9
# Reconstruire les objets choisis, pas seulement la valeur optimale
def sac_a_dos_avec_selection(poids: list[int], valeurs: list[int], capacite: int) -> tuple[int, list[int]]:
n = len(poids)
table = [[0] * (capacite + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for c in range(capacite + 1):
table[i][c] = table[i - 1][c]
if poids[i - 1] <= c:
table[i][c] = max(table[i][c], table[i - 1][c - poids[i - 1]] + valeurs[i - 1])
objets_choisis = []
c = capacite
for i in range(n, 0, -1):
if table[i][c] != table[i - 1][c]: # cet objet a été utilisé pour atteindre l'optimum
objets_choisis.append(i - 1)
c -= poids[i - 1]
return table[n][capacite], objets_choisis[::-1]
# --- Plus longue sous-séquence commune (LCS) : base du diff (git diff, etc.) ---
def plus_longue_sous_sequence_commune(a: str, b: str) -> int:
m, n = len(a), len(b)
table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1 # caractère commun : on étend la LCS
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1]) # sinon, meilleur des deux sous-problèmes
return table[m][n]
assert plus_longue_sous_sequence_commune("ABCBDAB", "BDCABA") == 4 # "BCBA" ou "BDAB"
def lcs_reconstruire(a: str, b: str) -> str:
m, n = len(a), len(b)
table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
# Remonter la table depuis (m, n) pour reconstruire la sous-séquence caractère par caractère
resultat = []
i, j = m, n
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
resultat.append(a[i - 1])
i -= 1; j -= 1
elif table[i - 1][j] > table[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(resultat))
assert lcs_reconstruire("ABCBDAB", "BDCABA") in ("BCBA", "BDAB")
# --- Distance d'édition (Levenshtein) : nombre minimal d'opérations pour transformer a en b ---
def distance_edition(a: str, b: str) -> int:
m, n = len(a), len(b)
table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
table[i][0] = i # supprimer les i premiers caractères de a
for j in range(n + 1):
table[0][j] = j # insérer les j premiers caractères de b
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] # rien à faire
else:
table[i][j] = 1 + min(
table[i - 1][j], # suppression
table[i][j - 1], # insertion
table[i - 1][j - 1], # substitution
)
return table[m][n]
assert distance_edition("chat", "chien") == 4Résumé
- Sac à dos 0/1 :
table[i][c]combine "prendre l'objet" vs "ne pas le prendre", O(n*capacité) temps et espace. - Parcourir la capacité à l'envers dans la version optimisée en espace évite de réutiliser un objet plusieurs fois.
- LCS et distance d'édition partagent le même schéma : une table 2D indexée par les préfixes des deux séquences.
- Reconstruire la solution (pas seulement sa valeur) nécessite de remonter la table de décision depuis le coin final.
Exercices pratiques
Mission : optimiser le chargement d'un camion de livraison
Objectif : Construire et remonter une table de sac à dos 0/1, puis relier LCS à un outil réel de comparaison de fichiers.
Contexte
Un camion de livraison a une capacité de 10 kg. Cinq colis sont disponibles avec (poids, valeur) : C1(2,3), C2(3,4), C3(4,5), C4(5,6), C5(6,8). L'objectif est de choisir un sous-ensemble de colis à charger qui maximise la valeur totale sans dépasser 10 kg, chaque colis étant pris entièrement ou pas du tout.