Choisir quoi emporter dans un sac trop petit paraît anodin. Pourtant, derrière cette situation se cache l’un des problèmes les plus étudiés en informatique et en recherche opérationnelle. Le problème du sac à dos sert à modéliser des décisions très concrètes : sélectionner des produits à charger, composer un portefeuille d’investissement, allouer un budget ou optimiser l’usage d’une mémoire limitée.
Le principe est simple à formuler. On dispose d’un ensemble d’objets, chacun ayant un poids et une valeur. Le sac possède une capacité maximale. L’objectif consiste à choisir les objets à placer dans le sac afin de maximiser la valeur totale, sans dépasser la capacité autorisée.
Dans sa version la plus connue, appelée sac à dos 0/1, chaque objet peut être pris une seule fois ou laissé de côté. Il n’est pas possible d’en prendre une fraction. Si un objet pèse 6 kg et vaut 30 points, il est soit inclus entièrement, soit exclu. Cette contrainte rend le problème plus difficile qu’il n’y paraît.
Un exemple suffit à le montrer. Avec une capacité de 10 kg, trois objets de poids 6, 5 et 5 kg, et de valeurs 30, 25 et 24, choisir l’objet le plus rentable ne garantit pas toujours la meilleure combinaison. La solution optimale dépend de l’ensemble des choix possibles, pas seulement du meilleur objet pris isolément.
La difficulté vient de l’explosion du nombre de combinaisons. Avec 10 objets, il existe déjà 1 024 sélections possibles. Avec 50 objets, le nombre dépasse le million de milliards. Tester toutes les solutions devient rapidement irréaliste, même pour un ordinateur performant.
Le problème du sac à dos 0/1 appartient à la famille des problèmes NP-difficiles dans sa version d’optimisation. Cela signifie qu’aucun algorithme connu ne permet de résoudre tous les cas efficacement en temps polynomial par rapport à la taille de l’entrée. En pratique, il faut donc choisir une méthode adaptée au contexte : solution exacte, approximation, heuristique ou combinaison de plusieurs approches.
Cette nuance est importante. Dire qu’un problème est difficile ne signifie pas qu’il est impossible à traiter. De nombreux cas réels se résolvent très bien, surtout lorsque la capacité du sac est raisonnable, que les poids sont entiers ou que l’on accepte une solution très proche de l’optimum.
La première idée consiste à énumérer toutes les combinaisons d’objets, puis à conserver celle qui offre la plus grande valeur sans dépasser la capacité. Cette méthode exhaustive a l’avantage d’être claire et fiable. Elle fournit toujours la solution optimale.
Son défaut est son coût. Pour n objets, il faut examiner 2 puissance n possibilités. Cette croissance exponentielle devient vite bloquante. Pour un petit ensemble d’objets, par exemple dans un exercice pédagogique ou un cas métier très limité, l’approche exhaustive reste acceptable. Au-delà, elle sert surtout de référence pour vérifier d’autres méthodes sur de petits jeux de données.
Dans les systèmes industriels, les décideurs n’ont généralement pas le luxe de parcourir toutes les combinaisons. Un entrepôt, une plateforme logistique ou un outil de planification budgétaire peut manipuler des centaines ou des milliers d’éléments. Il faut alors s’appuyer sur des stratégies plus intelligentes, capables d’éviter une exploration complète de l’espace des solutions.
Pour le sac à dos 0/1 avec des poids entiers, la programmation dynamique est l’une des méthodes les plus utilisées. Elle repose sur une idée efficace : résoudre progressivement des sous-problèmes plus petits et réutiliser leurs résultats au lieu de recalculer les mêmes combinaisons.
On construit généralement un tableau où les lignes représentent les objets considérés et les colonnes les capacités possibles du sac. À chaque étape, l’algorithme compare deux options : ne pas prendre l’objet courant, ou le prendre si sa taille le permet. Le meilleur choix est mémorisé. À la fin, la dernière case indique la valeur maximale atteignable.
Cette méthode est expliquée plus largement dans une ressource consacrée aux principes de mémorisation des sous-problèmes en optimisation, qui éclaire bien la logique derrière ce type d’algorithme.
Sa complexité est souvent notée O(nW), où n désigne le nombre d’objets et W la capacité du sac. Elle est donc très performante si W reste modéré. En revanche, si la capacité est immense, le tableau peut devenir coûteux en mémoire et en temps de calcul.
La programmation dynamique du sac à dos est parfois présentée comme rapide, mais il faut préciser ce que cela signifie. Sa complexité dépend de la valeur numérique de la capacité W, et non seulement du nombre de bits nécessaires pour représenter cette valeur. C’est pourquoi on parle de complexité pseudo-polynomiale.
Concrètement, une capacité de 10 000 peut se traiter facilement. Une capacité de plusieurs milliards, même avec peu d’objets, devient plus problématique si l’on construit un tableau pour toutes les capacités intermédiaires. L’efficacité dépend donc directement de l’échelle des données.
Cette notion est souvent source de confusion. Un algorithme pseudo-polynomial peut être excellent en pratique sur des données bien bornées, tout en ne constituant pas une solution polynomialement efficace au sens théorique. Pour approfondir ce point, l’article sur la différence entre temps polynomial et pseudo-polynomial apporte un cadre utile.
Une optimisation courante consiste à utiliser un tableau à une seule dimension plutôt qu’une matrice complète. En parcourant les capacités dans l’ordre décroissant, on évite de réutiliser plusieurs fois le même objet. Cette variante réduit fortement la mémoire nécessaire.
Une méthode gloutonne choisit à chaque étape l’option qui semble la meilleure localement. Pour le sac à dos, cela peut consister à trier les objets selon leur valeur, leur poids ou leur ratio valeur/poids, puis à les ajouter tant qu’il reste de la place.
Cette stratégie est très rapide. Elle donne même une solution optimale pour le sac à dos fractionnaire, où il est permis de prendre une partie d’un objet. Par exemple, si l’on transporte des matières premières divisibles, choisir d’abord les meilleurs ratios valeur/poids est pertinent.
Mais pour le sac à dos 0/1, la méthode gloutonne peut échouer. Un objet très rentable peut empêcher de prendre deux objets légèrement moins attractifs mais meilleurs ensemble. Cette limite est détaillée dans une analyse sur les cas où un choix local ne conduit pas à l’optimum global.
Les approches gloutonnes restent utiles pour obtenir rapidement une première solution, notamment dans des heuristiques ou des algorithmes hybrides. Elles peuvent aussi servir de borne initiale dans des méthodes exactes plus élaborées.
Lorsque la programmation dynamique n’est pas adaptée, une autre famille de méthodes entre en jeu : le branch and bound. L’idée consiste à explorer l’arbre des décisions tout en éliminant les branches qui ne peuvent pas mener à une meilleure solution que celle déjà connue.
Cette approche peut résoudre exactement de nombreux cas pratiques, surtout si les objets sont triés intelligemment et si de bonnes bornes supérieures sont calculées. Elle reste toutefois dépendante de la structure des données. Dans le pire des cas, l’exploration peut redevenir très lourde.
Pour les très grands problèmes, on accepte souvent une solution approchée. Les algorithmes d’approximation, dont certains schémas comme le FPTAS, permettent d’obtenir une solution dont la qualité est garantie à une marge près. Dans un contexte industriel, cette précision contrôlée peut être plus utile qu’un optimum exact obtenu trop tard.
Les heuristiques et métaheuristiques, comme la recherche locale, les algorithmes génétiques ou le recuit simulé, sont également utilisées lorsque le modèle se complique : contraintes multiples, objets incompatibles, volumes, délais, priorités ou incertitudes sur les valeurs.
Résoudre efficacement le problème du sac à dos commence par une question simple : quelle est la nature des données ? Si le nombre d’objets est faible, une recherche exhaustive peut suffire. Si les poids sont entiers et la capacité raisonnable, la programmation dynamique est souvent le meilleur choix.
Si les objets sont divisibles, la méthode gloutonne par ratio valeur/poids devient optimale. Si l’on traite un grand volume de données avec des contraintes complexes, une approximation ou une méthode hybride sera généralement plus réaliste. Le bon algorithme dépend donc autant des exigences métier que de la théorie.
Il faut aussi soigner la modélisation. Un problème de sac à dos peut être confondu avec d’autres problèmes d’optimisation, notamment en graphes. Les logiques ne sont pas les mêmes : un plus court chemin, par exemple, se traite avec des algorithmes spécialisés, comme l’illustre l’explication du calcul d’itinéraires optimaux dans un graphe pondéré.
En pratique, une démarche efficace consiste à commencer par un modèle clair, tester une solution simple, mesurer les performances, puis ajuster. Le problème du sac à dos est célèbre parce qu’il résume bien un défi courant : décider vite, sous contrainte, avec des ressources limitées et des arbitrages mesurables.
