Élagage
Leçon 11 sur 15 du cours Introduction à la programmation dynamique de Coddy.
L'élagage (pruning) est une technique utilisée pour réduire le nombre de calculs requis par un algorithme de programmation dynamique en évitant les calculs inutiles. Cela se fait en éliminant certaines branches de l'arbre récursif qui ne mèneront pas à une meilleure solution que la meilleure solution trouvée jusqu'à présent. L'élagage peut être utilisé dans les algorithmes de programmation dynamique tant descendants (top-down) qu'ascendants (bottom-up).
Défi
ExpertDans ce défi, on vous donne une matrice d'entiers et une valeur cible. Votre tâche consiste à choisir un entier dans chaque ligne de la matrice, de sorte que la différence absolue entre la valeur cible et la somme des entiers choisis soit minimisée. Vous devez ensuite renvoyer la valeur de cette différence absolue minimale.
Essayez vous-même
def minimize_difference(mat, target):
# Écrivez le code iciToutes les leçons de Introduction à la programmation dynamique
1Introduction à la programmation dynamique
Qu'est-ce que la programmation dynamique ?Pourquoi est-ce important ?Applications dans divers domaines3Algorithmes de programmation dynamique
Plus longue sous-suite communeProblème du sac à dosProblème du rendu de monnaieDistance d'édition