Le problème du sac à dos est l’un des problèmes les plus célèbres d’optimisation. En prépa, c’est le cas d’école pour comparer les stratégies, les algorithmes gloutons et les algorithmes dynamiques que nous allons présenter par la suite. C’est donc un super exercice pour s’exercer en Python en vue des concours. Présentons rapidement le problème et ses fondements mathématiques, avant de voir une méthode de résolution imparfaite en passant par un algorithme glouton, puis une méthode optimale par un algorithme dynamique.
Les fondements mathématiques
Formalisation du problème
Le problème du sac à dos se définit de la manière suivante : on considère un ensemble de \(n\) objets, où chaque objet \(i\) est caractérisé par une valeur \(v_i > 0\) et un poids \(w_i > 0\). On dispose d’un sac de capacité totale \(W\). Le but est de maximiser la somme des valeurs des objets emportés sans que leur poids total ne dépasse \(W\).
Mathématiquement, on cherche à maximiser la fonction objectif :
\[Z = \sum_{i=1}^{n} x_i v_i\]
sous la contrainte de capacité :
\[\sum_{i=1}^{n} x_i w_i \leq W \quad \text{avec} \quad x_i \in \{0, 1\} \quad \forall i \in \{1, \dots, n\}\]
La variable \(x_i = 1\) signifie que l’objet \(i\) est emporté et \(x_i = 0\) qu’il est laissé de côté. On parle de version 0/1 du problème, par opposition à la version continue où l’on pourrait emporter une fraction d’un objet.
Complexité combinatoire
Ce problème est dit combinatoire, car il existe \(2^n\) combinaisons possibles de vecteurs \(x\). En effet, choisir une sélection d’objets revient à choisir un sous-ensemble de l’ensemble total \(I = \{1, 2, \dots, n\}\). L’ensemble de toutes les combinaisons possibles est l’ensemble des parties de \(I\), noté \(\mathcal{P}(I)\), dont le cardinal vaut, d’après un résultat bien connu depuis la première année de prépa :
\[\text{Card}(\mathcal{P}(I)) = 2^n\]
Une recherche exhaustive qui testerait toutes les combinaisons est donc hors de question dès que \(n\) dépasse quelques dizaines : pour \(n = 50\), on dépasse \(10^{15}\) combinaisons, soit bien plus que ce qu’un ordinateur peut parcourir en un temps raisonnable. C’est ce qui motive le recours à des algorithmes plus intelligents.
Approche gloutonne
L’algorithme glouton repose sur une heuristique de choix local. Une approche heuristique désigne en effet des approches successives en éliminant progressivement les alternatives et en ne conservant qu’une gamme restreinte de solutions tendant vers celle qui est optimale. On définit l’indice de profitabilité \( r_i \) de chaque objet comme le ratio :
\[ r_i = \frac{v_i}{w_i} \]
L’algorithme trie les objets par \( r_i \) décroissant et les insère dans le sac tant que la place le permet.
En effet, une manière de mettre le plus de valeur dans le sac sous la contrainte de poids est de calculer le ratio \(\frac{valeur}{poids}\), de mettre l’objet avec ce plus gros ratio dans le sac, de mettre ensuite le deuxième (si on ne dépasse pas le poids total), et ainsi de suite.
Bien que cet algorithme soit optimal pour le « sac à dos continu » (où l’on peut couper les objets), il échoue pour le cas discret 0/1. L’écart entre la solution gloutonne et la solution optimale s’explique par la mauvaise gestion de l’espace résiduel : le glouton peut choisir un objet très « rentable » au kilo, mais qui prend une place telle qu’il empêche de mettre deux autres objets légèrement moins rentables mais plus précieux une fois cumulés.
Voici un exemple concret :
Soit W = 50 et on dispose des objets suivants : objet 1 (poids = 10, valeur = 60) → ratio = 6, objet 2 (poids = 20, valeur = 100) → ratio = 5 et objet 3 (poids = 30, valeur = 120) → ratio = 4.
Avec cet algorithme, on met le premier objet (ratio supérieur aux autres égal à 6), puis il reste de la place pour le deuxième (ratio de 5), mais il ne reste plus de place pour le troisième. On a donc une valeur cumulée dans le sac de 160, alors qu’on peut aisément vérifier (puisqu’on est en petite dimension) que la valeur optimale est de \(100 +120\) en cumulant les deux derniers objets pour un poids total de 50 exactement.
Il convient donc de voir désormais la méthode de résolution dynamique pour une résolution optimale de ce problème !
La programmation dynamique
Principe de la récurrence
Pour garantir l’optimum, on utilise la programmation dynamique, qui repose sur la décomposition du problème en sous-problèmes plus simples dont on mémorise les solutions. L’idée est de construire progressivement la solution optimale en exploitant la structure récursive du problème.
On note \(T[i][w]\) la valeur maximale que l’on peut obtenir en ne considérant que les \(i\) premiers objets et en disposant d’une capacité \(w\). Pour remplir ce tableau, on raisonne objet par objet : lorsque l’on considère l’objet \(i\), deux choix sont possibles.
Si on ne le prend pas, la valeur maximale reste celle obtenue sans lui : \(T[i-1][w]\).
Si on le prend (ce qui n’est possible que si \(w \geq w_i\)), la valeur totale est \(v_i + T[i-1][w – w_i]\), où \(T[i-1][w – w_i]\) représente le meilleur remplissage possible avec les objets précédents sur la capacité restante.
On prend le maximum des deux options, ce qui donne l’équation de récurrence fondamentale :
\[T[i][w] = \max\!\bigl(T[i-1][w],\; v_i + T[i-1][w – w_i]\bigr)\]
avec la convention \(T[0][w] = 0\) pour tout \(w\) (aucun objet disponible, valeur nulle) et \(T[i][0] = 0\) pour tout \(i\) (capacité nulle, valeur nulle).
Complexité et avantage sur le glouton
La programmation dynamique remplit un tableau de taille \((n+1) \times (W+1)\), ce qui représente \((n+1)(W+1)\) cases à calculer, chacune en temps constant. La complexité totale est donc plus grande que pour l’algorithme précédent.
L’avantage décisif sur le glouton est la garantie d’optimalité : en remplissant le tableau jusqu’à \(T[n][W]\), on obtient la valeur maximale exacte, sans approximation. Sur l’exemple précédent, la programmation dynamique trouve bien la valeur \(220\), là où le glouton s’arrêtait à \(160\), comme nous l’avons vu précédemment.
Ce script réplique donc exactement ce que nous venons de voir ci-dessus ! On a bien la matrice \(T\) dont chaque élément est rempli successivement grâce aux deux boucles « for i in range » imbriquées. Et chaque élément de \(T\) est bien rempli selon la formule que nous avons vu juste au dessus.
Conclusion
Le passage de l’algorithme glouton à la programmation dynamique illustre un principe fondamental en Python : la rapidité d’exécution et la garantie d’optimalité sont souvent en tension et le choix de la méthode dépend du contexte. Ce problème est donc à connaître sur le bout des doigts.
Il n’y a plus qu’à espérer qu’un tel thème tombe aux concours !
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
