problème du sac à dos

COMBINATOIRE

Le problème du sac à dos ou problème KP (Knapsack Problem) est un problème d’optimisation en algorithmique.
Enoncé : On dispose d’un certain nombre d’objets, chacun ayant un poids et une valeur. On doit mettre dans un sac à dos une partie de ces objets (ou tous) en maximisant la valeur totale et sans dépasser le poids que peut supporter le sac.
Cette formulation simple modélise des situations à solution complexe, c’est un problème de la classe des NP-complets .
Il est utilisé pour modéliser des situations telles que le chargement d’un bateau, la gestion d’un portefeuille, la découpe de matériaux, etc.