problème du sac à dos

Imaginez un sac limité à 7 kg et quatre objets pesant 3, 4, 5 et 1 kg. Chacun apporte une valeur différente. Le choix le plus précieux n'est pas forcément le meilleur, car il peut empêcher une combinaison plus avantageuse.

Le problème du sac à dos consiste à trouver la combinaison qui rapporte le plus sans franchir la limite de poids. Chaque objet est pris en entier ou laissé de côté. La difficulté vient du nombre de combinaisons à comparer, qui augmente très vite avec le nombre d'objets.

Dans la version dite 0-1, on dispose d'un nombre fini d'objets. Le nombre d'objets est noté n. L'objet numéro i possède un poids w_i et une valeur v_i, généralement non négatifs. La capacité du sac est notée C. La variable x_i vaut 1 si l'objet est retenu et 0 sinon. Les poids et les valeurs s'additionnent, et chaque objet peut être choisi au plus une fois.

Le programme d'optimisation s'écrit : La première somme est la valeur totale à maximiser. La seconde est le poids total, qui ne doit pas dépasser la capacité.

Dans le cadre standard où les poids, les valeurs, la capacité et la cible sont des entiers encodés en binaire, la formulation d'optimisation est NP-difficile ; sa version de décision, qui demande s'il existe un sous-ensemble de poids total au plus C et de valeur totale au moins égale à une cible V, est NP-complète. Une énumération exhaustive teste jusqu'à 2ⁿ sous-ensembles. Lorsque les poids et C sont des entiers de taille modérée, la programmation dynamique donne une solution exacte. Pour de très grandes instances, des heuristiques ou des algorithmes d'approximation recherchent plus vite une solution de bonne qualité, sans toujours garantir l'optimum exact.

Un sac peut porter 7 kg. Les données sont :
objet A : 3 kg, valeur 4 ;
objet B : 4 kg, valeur 5 ;
objet C : 5 kg, valeur 7 ;
objet D : 1 kg, valeur 1.

1. Le rapport valeur sur poids est 4/3 pour A, 5/4 pour B, 7/5 pour C et 1 pour D. Choisir d'abord le meilleur rapport retient C, puis D : le chargement pèse 6 kg et vaut 8.

2. Comparons les paires admissibles. A avec B pèse 3 + 4 = 7 kg et vaut 4 + 5 = 9. A avec D vaut 5, B avec D vaut 6, et C avec D vaut 8. Les autres paires dépassent 7 kg.

3. Le choix optimal est donc A et B : il remplit exactement le sac et atteint la valeur 9. Le choix glouton C et D reste admissible, mais sa valeur est inférieure d'une unité. Les deux chargements rendent visible cet écart.

4. Pour contrôler le résultat, aucune combinaison de trois objets ne convient : les trois plus légers pèsent déjà 1 + 3 + 4 = 8 kg. Les quatre objets ensemble pèsent 3 + 4 + 5 + 1 = 13 kg, donc dépassent aussi la capacité de 7 kg, et toutes les paires admissibles ont été comparées. La valeur 9 est donc bien l'optimum.

Pour charger un véhicule ou un navire, chaque lot peut recevoir un poids et une priorité. Le modèle convient si les lots sont indivisibles et qu'une capacité dominante limite le chargement. Si plusieurs volumes ou contraintes de sécurité interviennent, il faut un modèle à plusieurs contraintes.

Pour découper des matériaux, on peut choisir les pièces qui valorisent au mieux une quantité disponible. Le sac à dos est adapté à une ressource globale ; si l'emplacement précis des découpes compte, un modèle de découpe est nécessaire.

Pour allouer des ressources informatiques, une tâche peut avoir un coût en mémoire et un gain attendu. Une méthode exacte est utile lorsque la capacité entière reste modérée ; une heuristique devient préférable lorsque le nombre de choix ou le temps de calcul explose.

En gestion de portefeuille, poids et valeur peuvent représenter un budget et un objectif. Ce modèle ne suffit que si ces quantités sont additives et les choix discrets. Des risques liés entre eux appellent un modèle financier plus riche.

Sac à dos 0-1 et sac à dos fractionnaire. Dans le premier, un objet est pris en entier ou refusé ; dans le second, une fraction peut être prise. Avec l'exemple conducteur, fractionner B après avoir choisi C est permis seulement dans la version fractionnaire.

Problème du sac à dos et rangement dans des boîtes. Le sac à dos maximise une valeur dans une capacité donnée. Le rangement dans des boîtes cherche plutôt à placer tous les objets en utilisant le moins de contenants possible.

Heuristique et algorithme d'approximation. Une heuristique vise rapidement une bonne solution sans garantie générale. Un algorithme d'approximation fournit une borne démontrée sur l'écart à l'optimum. Obtenir 8 au lieu de 9 ne suffit pas, à lui seul, à prouver une garantie valable pour tous les cas.

La qualification de complexité demande de préciser la question. Un algorithme d'optimisation cherche la meilleure valeur ; un problème de décision répond oui ou non pour une cible fixée. C'est la version de décision qui est NP-complète, tandis que l'optimisation est NP-difficile.

Le meilleur rapport valeur sur poids ne garantit pas l'optimum en 0-1. Dans l'exemple, cette règle choisit C puis D et obtient 8, alors que A avec B donne 9. Il faut une méthode exacte ou une garantie adaptée si l'optimum est exigé.

La programmation dynamique n'est pas polynomiale en la longueur binaire de la capacité. Pour des poids entiers, son temps usuel est proportionnel au produit du nombre d'objets n par la capacité entière C. Elle est dite pseudo-polynomiale : une capacité numériquement immense peut rendre le calcul impraticable même avec peu d'objets.

Les données dégénérées doivent être traitées explicitement. Si C = 0, aucun objet de poids strictement positif ne peut entrer. Un objet de poids nul et de valeur positive est retenu d'office dans la version 0-1 ; autoriser des copies illimitées changerait le problème et pourrait rendre la valeur sans borne.

La programmation dynamique explique comment mémoriser des sous-problèmes pour obtenir une solution exacte lorsque les poids et la capacité sont des entiers gérables.

L'article Les métaheuristiques prolonge le cas des grandes instances, lorsque rechercher efficacement une très bonne solution devient plus réaliste que garantir l'optimum.