Le problème du sac à dos

Une randonneuse avec une limite de poids, un voleur avec un sac, une entreprise avec un budget et une liste de projets : tous se posent la même question. Que faut-il prendre pour obtenir le plus de valeur sans dépasser la limite ? C'est le problème du sac à dos, et la programmation dynamique le résout exactement quand les poids sont des nombres entiers de taille modérée.

Un tableau avec une ligne par objet et une colonne par capacité, le chemin de remontée en orange, à côté d'un sac et d'objets de différentes tailles
Un tableau avec une ligne par objet et une colonne par capacité, le chemin de remontée en orange, à côté d'un sac et d'objets de différentes tailles

Le problème

Il y a n objets, chacun avec un poids et une valeur, et un sac qui supporte au plus un poids W. Choisissez un ensemble d'objets dont le poids total est au plus W et dont la valeur totale est la plus grande possible. Chaque objet entre en entier ou reste dehors, d'où le nom de problème du sac à dos 0/1. Avec n objets, il y a 2ⁿ ensembles possibles, donc les essayer tous devient vite impossible.

Le tableau

Soit best[i][w] la plus grande valeur qui tient dans le poids w en utilisant seulement les i premiers objets. Alors best[0][w] = 0, et pour chaque ligne suivante il y a deux choix : laisser l'objet i de côté, ce qui donne best[i − 1][w], ou, si son poids wᵢ tient, le mettre dans le sac, ce qui donne sa valeur plus best[i − 1][w − wᵢ]. La plus grande des deux est best[i][w]. En remplissant le tableau ligne par ligne, les deux cases nécessaires sont toujours prêtes.

Un exemple

Prenons une capacité de 7 et quatre objets de poids 1, 3, 4 et 5 et de valeurs 1, 4, 5 et 7. Avec seulement le premier objet, chaque capacité à partir de 1 vaut 1. En ajoutant le deuxième, la capacité 4 peut contenir les deux pour 5. En ajoutant le troisième, la capacité 7 peut contenir les objets 2 et 3 pour 9. Le quatrième objet, de poids 5 et de valeur 7, pourrait rejoindre l'objet 1 pour 8 avec une capacité de 6 ou 7, mais 9 est mieux, donc la case en bas à droite vaut 9 : on prend les objets de poids 3 et 4.

Est-ce difficile ?

Le tableau demande environ n·W étapes. Cela semble rapide, mais W est un nombre, et un nombre à d chiffres peut atteindre 10 puissance d, donc le travail croît de façon exponentielle avec la longueur de l'entrée. Le problème du sac à dos est NP-difficile ; il faisait partie des 21 problèmes NP-complets de Richard Karp en 1972. En pratique, le tableau, la méthode de séparation et évaluation et de bons schémas d'approximation traitent bien de grandes instances réelles.

Histoire et applications

Le nom remonte au mathématicien Tobias Dantzig au début du XXe siècle, et son fils George Dantzig en a donné une méthode gloutonne classique en 1957. Les problèmes de sac à dos apparaissent dans l'établissement de budgets et le choix de portefeuilles, dans la découpe de matières premières avec le moins de chutes possible, dans le chargement de marchandises, et même dans les débuts de la cryptographie à clé publique : le cryptosystème de Merkle–Hellman de 1978 reposait sur un problème de sac à dos, et il a été cassé quelques années plus tard.

George Dantzig (à gauche) recevant la National Medal of Science du président Gerald Ford en 1976. En 1957, Dantzig donna une méthode gloutonne classique pour le problème du sac à dos. Le nom lui-même remonte à son père, Tobias Dantzig.
George Dantzig (à gauche) recevant la National Medal of Science du président Gerald Ford en 1976. En 1957, Dantzig donna une méthode gloutonne classique pour le problème du sac à dos. Le nom lui-même remonte à son père, Tobias Dantzig.

À vous de jouer

Ouvrez l'application, passez à la vue Tableau et appuyez sur Étape. La case orange est en cours de remplissage, et les cases bleues sont les deux qu'elle compare : la case juste au-dessus et, dans la ligne du dessus, la case décalée vers la gauche du poids de l'objet. Après la dernière case, la remontée part du coin en bas à droite, en orange, et les objets mis dans le sac apparaissent sous le tableau.

Questions fréquemment posées

Quelle est la différence entre le sac à dos 0/1, borné et non borné ?

Dans la version 0/1, chaque objet est pris au plus une fois. Dans la version bornée, chaque objet existe en un nombre limité d'exemplaires, et dans la version non bornée en nombre illimité. Le tableau ne change que légèrement de l'une à l'autre.

La méthode gloutonne est-elle parfois juste pour le sac à dos ?

Pour le problème du sac à dos fractionnaire, où l'on peut couper les objets, prendre d'abord la meilleure valeur par poids est optimal. Pour des objets entiers, elle peut être très loin du compte, même si la meilleure des deux solutions entre la méthode gloutonne et l'objet le plus précieux pris seul vaut toujours au moins la moitié de la meilleure valeur.

De combien de mémoire le tableau a-t-il besoin ?

(n + 1)·(W + 1) cases pour le tableau complet, ce qu'il faut pour retrouver les objets. Si l'on veut seulement la meilleure valeur, une ligne de W + 1 cases suffit, remplie de droite à gauche.

Le sac à dos est-il la même chose que la somme de sous-ensemble ?

La somme de sous-ensemble est le cas particulier où la valeur de chaque objet est égale à son poids et où la question est de savoir si l'on peut remplir le sac exactement. Ce problème est lui aussi NP-complet et se résout avec le même genre de tableau.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer le problème du sac à dos