Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème du sac à dos
Résumé
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.
L'objectif du problème du sac à dos est de sélectionner des objets à mettre dans le sac à dos de façon à maximiser la somme des valeurs des objets pris, sous la contrainte que le poids total des objets pris ne dépasse pas la capacité du sac à dos. Ce problème est NP-complet. Ainsi, il est difficile à résoudre, en particulier pour les grands ensembles d'objets.
Pour résoudre le problème du sac à dos, il existe plusieurs algorithmes et approches différentes, notamment la programmation dynamique, les algorithmes gloutons et la programmation en nombres entiers. Ces algorithmes peuvent être appliqués à un large éventail de problèmes réels, tels que préparer une valise pour un voyage, allouer des ressources dans une chaîne d'approvisionnement et optimiser la gestion des stocks.
Le problème du sac à dos est l'un des 21 problèmes NP-complets de Richard Karp, exposés dans son article de 1972.
Il est intensivement étudié depuis le milieu du et on trouve des références dès 1897, dans un article de . La formulation du problème est fort simple, mais sa résolution est plus complexe. Les algorithmes existants peuvent résoudre des instances pratiques de taille importante. Cependant, la structure singulière du problème, et le fait qu'il soit présent en tant que sous-problème d'autres problèmes plus généraux, en font un sujet de choix pour la recherche.
Ce problème est à la base du premier algorithme de chiffrement asymétrique (ou à « clé publique ») présenté par Martin Hellman, Ralph Merkle et Whitfield Diffie à l'université Stanford en 1976.
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.