Douze objets, une capacité, et une question qui résiste depuis soixante ans.
Des objets, chacun avec un poids et une valeur ; un sac qui ne supporte qu'une charge donnée. Que emporter ? L'énoncé est celui d'un jeu d'enfant, et le problème est NP-difficile : personne ne connaît d'algorithme rapide qui le résolve toujours, et personne ne sait démontrer qu'il n'en existe pas.
maximiser Σ vi xi sous Σ wi xi ≤ C xi ∈ {0, 1}
Tout tient dans ce petit ensemble {0, 1}. Remplacez-le par l'intervalle [0, 1] — autorisez à couper les objets — et le problème devient trivial : on trie par valeur au kilo et l'on remplit. C'est l'indivisibilité, et elle seule, qui fait toute la difficulté. Les cinq planches parcourent la panoplie complète : ce que donne le bon sens, ce que donne la récurrence, ce que donne l'exploration organisée, ce que deviennent les variantes — et pour finir, où se cachent les instances vraiment difficiles.
La règle naturelle est de trier les objets par valeur au kilo et de les prendre tant qu'ils rentrent. Cette règle est exactement optimale pour le problème fractionnaire — on remplit le sac jusqu'à la gueule, en coupant le dernier objet — et cette valeur fractionnaire est donc une borne supérieure imprenable pour le problème entier. Entre les deux se loge l'écart d'intégrité, tout l'enjeu du sujet.
La « garantie du glouton amélioré » mérite une explication. Le glouton seul n'offre aucune garantie — il peut être arbitrairement mauvais. Mais si l'on prend le meilleur des deux entre le résultat glouton et le seul objet le plus précieux qui rentre, on obtient toujours au moins la moitié de l'optimum. C'est le plus simple des algorithmes d'approximation à garantie, et la page vérifie ce rapport de 1/2 sur chaque instance tirée.
Notons M(i, c) la meilleure valeur atteignable avec les i premiers objets et une capacité c. Pour l'objet i, il n'y a que deux possibilités — le prendre ou pas :
M(i, c) = max( M(i−1, c) , vi + M(i−1, c − wi) )
Une comparaison par case, n·C cases : le tableau se remplit et la dernière case donne l'optimum. Mais il existe une seconde récurrence, symétrique : au lieu de demander la meilleure valeur pour une capacité donnée, on demande le poids minimal pour atteindre une valeur donnée. Elle coûte n·V. Selon que les poids ou les valeurs sont les plus gros nombres, l'une écrase l'autre.
L'arbre des décisions a 2n feuilles : prendre ou laisser chaque objet. On peut pourtant n'en visiter qu'une poignée, grâce à une idée en deux temps. Séparer : à chaque nœud, on choisit un objet et l'on ouvre deux branches. Évaluer : sur chaque branche, on calcule la borne fractionnaire de ce qu'on peut espérer au mieux en poursuivant. Si cette borne ne dépasse pas la meilleure solution déjà trouvée, toute la branche est inutile — on l'élague sans l'explorer.
Autorisons maintenant à prendre plusieurs exemplaires du même objet : c'est le sac à dos non borné, et sa récurrence se simplifie — une seule dimension suffit. Poussons plus loin en oubliant les valeurs pour ne garder que les poids : quelles sommes exactes peut-on former ? C'est la somme de sous-ensembles, et sa version illimitée est le problème du rendu de monnaie, dont la réponse cache un joli théorème d'arithmétique.
Le nombre affiché en rouge est le nombre de Frobenius du système de pièces : la plus grande somme qu'on ne puisse pas former. Il n'existe que si les pièces sont premières entre elles — sinon aucun multiple étranger au pgcd n'est atteignable, et il y a une infinité de sommes impossibles. Avec 6, 9 et 20, il vaut 43 : c'est le fameux nombre associé aux boîtes de nuggets, qui se vendaient autrefois par 6, 9 ou 20.
Un problème NP-difficile n'est pas difficile partout. La plupart des sacs à dos tirés au hasard se résolvent en quelques dizaines de nœuds. Les instances qui résistent ont deux caractéristiques précises, et la page les met en évidence l'une après l'autre.
D'abord la corrélation : si la valeur d'un objet est à peu près proportionnelle à son poids, tous les sous-ensembles de même poids se valent, la borne fractionnaire ne discrimine plus rien, et l'élagage s'effondre. Ensuite la capacité : le pire cas se trouve autour de la moitié du poids total, là où le nombre de sous-ensembles candidats est maximal. Aux deux extrémités, tout est facile — un sac minuscule ou un sac qui contient tout ne posent aucune question.
La programmation dynamique résout le sac à dos en n·C opérations. Voilà qui a l'air polynomial — et qui règlerait la question P contre NP si c'en était. Le piège est là : C n'est pas la taille de l'énoncé. Écrire une capacité de un million demande sept chiffres, pas un million. Multiplions tous les poids par dix, l'énoncé s'allonge d'un caractère par nombre et le tableau devient dix fois plus grand. L'algorithme est polynomial en la valeur des nombres, exponentiel en leur longueur.
Les trois courbes racontent trois natures d'algorithme. La dynamique monte tout droit avec la valeur des nombres — elle est excellente tant que les poids sont petits, désastreuse dès qu'ils sont gros. La force brute ne bouge pas d'un pouce : elle ne regarde que le nombre d'objets, et le paie très cher. La séparation-évaluation, elle, reste au ras du sol dans les deux cas — c'est pourquoi les solveurs industriels reposent sur elle et non sur le tableau. Un algorithme n'est pas rapide ou lent dans l'absolu : il l'est relativement à ce qui, dans l'énoncé, se met à grandir.