Séance de cours

Problème de Knapsack : Programmation dynamique

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

Cette séance de cours couvre le concept de programmation dynamique appliquée au problème Knapsack, en se concentrant sur la recherche de la solution optimale en considérant le poids total accumulé par les éléments. Il explique le processus de construction d'un graphique acyclique dirigé et de détermination de la solution optimale par une programmation dynamique. La séance de cours examine également le plus petit sous-ensemble de poids avec un bénéfice spécifique et présente des algorithmes pour résoudre le problème Knapsack efficacement.

Source officielle

Concepts associés (23)

Graphe orienté acyclique

En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.

Graphe orienté

thumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.

Arbre (théorie des graphes)

En théorie des graphes, un arbre est un graphe acyclique et connexe. Sa forme évoque en effet la ramification des branches d'un arbre. Par opposition aux arbres simples, arbres binaires, ou arbres généraux de l'analyse d'algorithme ou de la combinatoire analytique, qui sont des plongements particuliers d'arbres (graphes) dans le plan, on appelle parfois les arbres (graphes) arbres de Cayley, car ils sont comptés par la formule de Cayley. Un ensemble d'arbres est appelé une forêt.

Cycle (théorie des graphes)

thumb|Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle. Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).

Problème du sac à dos

En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.

Afficher plus

Séances de cours associées (64)

Programmation dynamique: Knapsack

Explore la programmation dynamique du problème Knapsack, en discutant des stratégies, des algorithmes, de la dureté du NP et de l'analyse de la complexité temporelle.

Réseaux bayésiens : factorisation et échantillonnage

Explique les méthodes de factorisation et d'échantillonnage des réseaux bayésiens à l'aide des GAD et de l'élimination des variables.

DFS Continuation : Tri topologique

Couvre des sujets tels que la sortie DFS, la classification des bords, les graphes acycliques, l'exactitude, l'analyse du temps, les SCC et l'algorithme de tri topologique.

Qu’est-ce qu’une preuve formelle?

Couvre le concept de systèmes de preuve formelle, leur structure et leur solidité.

Inférence causale & Graphiques dirigés

Explore l'inférence causale, les graphiques dirigés et l'équité dans les algorithmes, en mettant l'accent sur l'indépendance conditionnelle et les implications des GAD.

Afficher plus

Concepts associés (23)

Graphe orienté acyclique

Graphe orienté

Arbre (théorie des graphes)

Cycle (théorie des graphes)

Problème du sac à dos

Afficher plus