9. Programmation dynamique

Revenons au problème du sac à dos du chapitre 8. Vous êtes un voleur avec un sac à dos pouvant transporter 4 kg de marchandises.Il y a trois articles que vous pouvez mettre dans le sac à dos.
Quels objets dérober pour que le butin représente le plus d’argent possible ?
L’algorithme le plus simple est le suivant : vous essayez tous les ensembles d’articles possibles et trouvez celui qui a la plus forte valeur.
Cela fonctionne, mais c’est vraiment lent. Pour 3 articles, vous devez calculer 8 assortiments possibles. Pour 4 articles, vous devez en calculer 16. Avec chaque élément que vous ajoutez, le nombre d’ensembles que vous devez calculer double ! Cet algorithme prend un temps O(2n), ce qui est très, très lent.C’est peu pratique pour n’importe quel nombre raisonnable de biens. Au chapitre 8, vous avez vu comment calculer une solution approximative. Cette solution sera proche de la solution optimale, mais ce n’est peut-être pas la solution optimale.
Alors comment calculer la solution optimale ?
Réponse : avec la programmation dynamique ! Voyons comment fonctionne l’algorithme de programmation dynamique ici. La programmation dynamique commence par résoudre des sous-problèmes et se développe pour résoudre le problème principal.
Pour le problème du sac à dos, vous commencerez par résoudre le problème de sacs à dos plus petits (ou « sous-sacs à dos »), puis travaillerez jusqu’à résoudre le problème d’origine.La programmation dynamique est un concept difficile, alors ne vous inquiétez pas si vous ne comprenez pas tout de suite…