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.
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.
À 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