Sac à dos 0/1 : implémentation et complexité (dynamique)

1. De la Récurrence à la Table de Programmation Dynamique

Pour rappel, la relation de récurrence que nous avons établie est la suivante. Si nous notons $K(i,w)$ la valeur maximale que l'on peut obtenir en utilisant les $i$ premiers objets avec une capacité de sac de $w$, alors :

où $p_i$ et $v_i$ sont le poids et la valeur de l'objet $i$.

L'approche par tabulation (ou bottom-up) consiste à construire une table, ou une matrice, pour stocker les solutions des sous-problèmes.

• Les lignes de la table correspondront aux objets considérés (de 0 à $n$).
• Les colonnes correspondront aux capacités du sac (de 0 à $W$).

La cellule K[i][w] de la table contiendra donc la valeur de $K(i,w)$. Nous remplirons cette table itérativement, en partant des cas de base (K[0][w] = 0 et K[i][0] = 0) jusqu'à atteindre la cellule K[n][W], qui contiendra notre solution finale.

L'image ci-dessous illustre la structure de cette table.

Pour voir ce processus de remplissage en action, la vidéo suivante est un excellent support. Elle détaille, case par case, comment la table est construite.

2. Implémentation de l'Algorithme et Analyse de Complexité

Maintenant que le principe de la tabulation est clair, nous pouvons passer à l'implémentation. Le document suivant, issu d'un support de préparation français, propose une implémentation Python très directe.

Le code que vous venez d'étudier se compose de deux boucles imbriquées. Analysons sa complexité :

• Complexité temporelle : La boucle externe itère sur les objets, de 1 à $n$. La boucle interne itère sur les capacités, de 1 à $W$. Le corps de la boucle effectue des opérations en temps constant. La complexité temporelle est donc de $O(n\cdot W)$.
• Complexité spatiale : Nous stockons une table de taille $(n+1)\times (W+1)$. La complexité spatiale est donc également de $O(n\cdot W)$.

Une remarque importante pour l'Agrégation : cette complexité est qualifiée de pseudo-polynomiale. Bien qu'elle semble polynomiale en $n$ et $W$, elle dépend de la valeur de $W$. Si $W$ est très grand (par exemple, de l'ordre de $2^n$), l'algorithme devient exponentiel par rapport à la taille de l'entrée en binaire.

3. Reconstruire la Solution

L'algorithme nous donne la valeur maximale, mais ne nous dit pas quels objets ont été choisis. Pour le savoir, il faut "remonter" la table à partir de la dernière case K[n][W].

L'idée est simple : pour chaque objet $i$ (en partant de $n$), si K[i][w] != K[i-1][w], cela signifie que la valeur a changé à l'étape $i$, et donc que l'objet $i$ a été inclus dans la solution optimale pour cette capacité. On l'ajoute à notre liste de solution, on décrémente la capacité de son poids, et on continue à l'étape $i-1$.

Le document Programmation Dynamique - Problème du Sac à Dos (ressource LINK) que vous avez consulté précédemment contient, dans sa section 2.6 (Listing 2), une version modifiée du code qui implémente cette logique de reconstruction. Jetez-y un œil pour voir comment cela se traduit concrètement.

4. Optimisation de la Complexité Spatiale

Une complexité spatiale en $O(n\cdot W)$ peut être problématique si $W$ est grand. Observons notre récurrence : pour calculer la ligne $i$, nous n'avons besoin que des informations de la ligne $i-1$. Il est donc inutile de conserver toute la table en mémoire.

Optimisation à 2 lignes :
On peut réduire l'espace à $O(W)$ en n'utilisant que deux tableaux d'_ taille $W+1$ : un pour la ligne i-1 (précédente) et un pour la ligne i (actuelle).

Optimisation à 1 ligne :
On peut pousser l'optimisation encore plus loin et n'utiliser qu'un seul tableau de taille $W+1$. L'astuce est de parcourir la boucle interne (sur les capacités $w$) à l'envers, de $W$ vers le poids de l'objet courant. Ceci garantit que lorsqu'on calcule K[w], la valeur K[w - p_i] que l'on utilise est bien celle de l'itération précédente (la ligne $i-1$) et non celle que l'on viendrait de mettre à jour à l'itération actuelle.

Cette technique est subtile mais très classique. La vidéo suivante l'explique de manière exceptionnellement claire.

Avec cette optimisation, la complexité spatiale est réduite à $O(W)$, tandis que la complexité temporelle reste $O(n\cdot W)$.

Conclusion

Aujourd'hui, vous avez accompli une étape fondamentale en passant de la théorie à la pratique.

Points clés à retenir :

• La solution par tabulation pour le sac à dos consiste à remplir une table $K[i][w]$ de manière itérative, en appliquant la relation de récurrence à chaque cellule.
• L'algorithme de base a une complexité temporelle et spatiale de $O(n\cdot W)$. C'est une complexité dite pseudo-polynomiale.
• Il est possible (et souvent attendu) d'optimiser la complexité spatiale à $O(W)$ en observant que le calcul de chaque ligne ne dépend que de la précédente.
• L'optimisation la plus élégante n'utilise qu'un seul tableau et requiert une itération inversée sur les capacités pour garantir la correction.

Pour un concours comme l'Agrégation, il ne suffit pas de savoir implémenter un algorithme. Il faut aussi être capable de prouver qu'il est correct. Dans notre prochaine leçon, nous nous attacherons à cet aspect formel en rédigeant une preuve de correction par récurrence pour l'algorithme du sac à dos, une compétence essentielle pour démontrer la profondeur de votre compréhension.