Séance de cours
Programmation dynamique: Knapsack
Description
Cette séance de cours couvre le concept de programmation dynamique appliquée au problème de Knapsack, où des éléments avec des poids et des profits différents doivent être sélectionnés pour maximiser le profit dans une capacité donnée. L'instructeur explique le processus étape par étape, de la définition du problème à la recherche de la solution optimale à l'aide de la programmation dynamique. Diverses stratégies et algorithmes sont discutés, y compris les problèmes difficiles du NP et l'analyse de la complexité du temps. La séance de cours se termine par le calcul du chemin le plus long dans un graphique acyclique dirigé pour résoudre efficacement le problème de Knapsack.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.