Définition - Que signifie le problème du sac à dos?
Le problème du sac à dos est un problème d'optimisation utilisé pour illustrer à la fois le problème et la solution. Il tire son nom d'un scénario où l'on est contraint dans le nombre d'articles qui peuvent être placés dans un sac à dos de taille fixe. Étant donné un ensemble d'articles avec des poids et des valeurs spécifiques, le but est d'obtenir autant de valeur dans le sac à dos que possible compte tenu de la contrainte de poids du sac à dos.
Definir Tech explique le problème du sac à dos
Le problème du sac à dos est un exemple de problème d'optimisation combinatoire, un sujet en mathématiques et en informatique sur la recherche de l'objet optimal parmi un ensemble d'objets. C'est un problème qui a été étudié pendant plus d'un siècle et qui est un problème d'exemple couramment utilisé en optimisation combinatoire, où il y a un besoin pour un objet optimal ou une solution finie où une recherche exhaustive n'est pas possible. Le problème peut être trouvé dans des scénarios du monde réel comme l'allocation des ressources dans les contraintes financières ou même dans la sélection des investissements et des portefeuilles. Il peut également être trouvé dans des domaines tels que les mathématiques appliquées, la théorie de la complexité, la cryptographie, la combinatoire et l'informatique. C'est de loin le problème le plus important en logistique.
Dans le problème du sac à dos, les articles donnés ont au moins deux attributs: la valeur d'un article, qui affecte son importance, et le poids ou le volume d'un article, qui est son aspect de limitation. Puisqu'une recherche exhaustive n'est pas possible, on peut diviser les problèmes en sous-problèmes plus petits et l'exécuter de manière récursive. C'est ce qu'on appelle une sous-structure optimale. Cela ne concerne qu'un seul article à la fois et le poids actuel encore disponible dans le sac à dos. Le résolveur de problèmes n'a qu'à décider s'il doit prendre ou non l'article en fonction du poids qui peut encore être accepté. Cependant, s'il s'agit d'un programme, le recalcul n'est pas indépendant et poserait des problèmes. C'est là que les techniques de programmation dynamique peuvent être appliquées. Les solutions à chaque sous-problème sont stockées de sorte que le calcul ne doive se produire qu'une seule fois.