Au programme de ce chapitre
- I. Principe : sous-problèmes chevauchants et sous-structure optimale
- II. Exemple complet : le problème du sac à dos
- III. Complexité et comparaison avec la force brute
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition La programmation dynamique résout un problème en le décomposant en sous-problèmes, comme « diviser pour régner », mais s'applique lorsque ces sous-problèmes se chevauchent : les mêmes sous-problèmes reviennent plusieurs fois. L'idée est de calculer chaque sous-problème une seule fois et de mémoriser son résultat dans un tableau, pour ne jamais le recalculer.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3, avec quatre objets A (poids 3, valeur 4), B (poids 4, valeur 5), C (poids 2, valeur 3) et D (poids 5, valeur 8), pour un sac de capacité 8 :
>>> objets = [("A", 3, 4), ("B", 4, 5), ("C", 2, 3), ("D", 5, 8)]
>>> capacite = 8
>>> def sac_a_dos_dp(objets, capacite):
... n = len(objets)
... dp = [[0] * (capacite + 1) for _ in range(n + 1)]
... for i in range(1, n + 1):
... nom, poids, valeur = objets[i - 1]
... for c in range(capacite + 1):
... if poids <= c:
... dp[i][c] = max(dp[i-1][c], dp[i-1][c-poids] + valeur)
... else:
... dp[i][c] = dp[i-1][c]
... return dp[n][capacite]
...
>>> sac_a_dos_dp(objets, capacite)
12dp où dp[i][c] représente la meilleure valeur atteignable en n'utilisant que les i premiers objets, avec une capacité c. La ligne de récurrence compare deux choix pour l'objet i : ne pas le prendre (on garde dp[i-1][c]), ou le prendre si son poids le permet (on ajoute sa valeur à la meilleure solution restant avec la capacité réduite, dp[i-1][c-poids] + valeur). La solution optimale, de valeur 12, correspond au choix des objets A et D : poids 3 + 5 = 8 (qui remplit exactement le sac) pour une valeur 4 + 8 = 12. On a vérifié par force brute (en testant les 2⁴ = 16 sous-ensembles possibles) que cette valeur 12 est bien la meilleure possible.Les erreurs fréquentes à éviter
Piège. Sans mémoïsation, un calcul récursif de Fibonacci recalcule les mêmes valeurs un nombre exponentiel de fois.
Attention La programmation dynamique ne s'applique que si le problème possède une sous-structure optimale : la solution optimale globale doit pouvoir se construire à partir de solutions optimales de sous-problèmes. Ce n'est pas toujours vrai : il faut le vérifier avant d'appliquer la méthode, sous peine d'obtenir un résultat faux.
L'astuce du prof
Astuce. Repère les sous-problèmes qui reviennent : s'ils se répètent, stocke leurs résultats (mémoïsation).
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Quel est l'intérêt de la mémoïsation pour calculer Fibonacci ?
Voir la correction
Elle évite de recalculer plusieurs fois les mêmes termes : on stocke chaque résultat, ce qui accélère énormément le calcul.
Exercice 2
Quelle est l'idée de la programmation dynamique ?
Voir la correction
Réutiliser les résultats de sous-problèmes déjà résolus, au lieu de les recalculer.