∑
MathTCG
#040 / 100•Algebra & Numbers•MathTCG #340 / 500•★★Peu commune•⊦Maths Discrètes•Concept

Problème du sac à dos

Période historique : 1972

Problème d'optimisation combinatoire NP-complet cherchant à maximiser la valeur sous contrainte de poids.

Contenu & Formulation mathématique

Définition rigoureuse
Problème d'optimisation linéaire en nombres entiers binaires à contrainte de sacoche.
Notation usuelle & Exemples
x_i \in \{0, 1\}
max⁡∑i=1nvixisous contrainte∑i=1nwixi≤W,  xi∈{0,1}\max \sum_{i=1}^n v_i x_i \quad \text{sous contrainte} \quad \sum_{i=1}^n w_i x_i \le W, \; x_i \in \{0, 1\}

Genèse & Portée historique

Étant donné un ensemble d'objets ayant chacun un poids et une valeur, le problème consiste à choisir un sous-ensemble d'objets maximisant la valeur totale sans dépasser une capacité maximale de poids W. C'est l'un des 21 problèmes NP-complets initiaux de Richard Karp.

Bien que NP-complet, il admet un algorithme de résolution pseudo-polynomial en O(nW) par programmation dynamique et des schémas d'approximation PTAS très efficaces.

« Faire le tri optimal face à la contrainte impitoyable de la capacité finie. »

Filiations & Relations conceptuelles (0)

Cette notice constitue un axiome autonome sans relations directes enregistrées dans le recueil.

Objet de collection MathTCG

#340
★★Peu commune
⊦

Problème du sac à dos

Maths Discrètes•CONCEPT

Problème d'optimisation linéaire en nombres entiers binaires à contrainte de sacoche.

max⁡∑i=1nvixisous contrainte∑i=1nwixi≤W,  xi∈{0,1}\max \sum_{i=1}^n v_i x_i \quad \text{sous contrainte} \quad \sum_{i=1}^n w_i x_i \le W, \; x_i \in \{0, 1\}
1972

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Algebra & Numbers.

Extension : Algebra & Numbers (#040 / 100)
Numéro global MathTCG : MathTCG #340 / 500
Rareté officielle : Peu commune (★★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : probleme-du-sac-a-dos
Consulter mon classeurExplorer tout le recueil