Sac à dos 0/1 et optimisation de l’espace

Le problème du sac à dos 0/1 consiste, étant donné n éléments dotés chacun d’un poids w[i] et d’une valeur v[i], ainsi qu’un sac à dos de capacité W, à choisir des éléments afin de maximiser la valeur totale sans dépasser la capacité. Chaque élément est pris exactement une fois (0 = ne pas le prendre, 1 = le prendre). Il s’agit de l’exemple fondateur de toute une famille de problèmes de DP posés en entretien, notamment la partition en sous-ensembles de somme égale et la somme cible.

Définissez dp[i][c] comme la valeur maximale obtenue en utilisant les i premiers éléments avec une capacité c. Pour l’élément i, deux choix sont possibles : ne pas le prendre (dp[i-1][c]) ou le prendre si w[i] <= c (dp[i-1][c-w[i]] + v[i]). La récurrence est la suivante : dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) lorsque w[i] <= c, sinon dp[i][c] = dp[i-1][c]. Cas de base : dp[0][c] = 0 pour tout c.

La table en 2D contient (n+1) x (W+1) entrées et se remplit ligne par ligne pour chaque élément. Une fois toutes les lignes remplies, dp[n][W] contient la valeur maximale. L’algorithme s’exécute en O(n × W) en temps et utilise O(n × W) d’espace — une complexité pseudo-polynomiale efficace lorsque W est petit.

L’observation essentielle est la suivante : la ligne i ne dépend que de la ligne i-1. Nous pouvons donc utiliser un seul tableau en 1D et le mettre à jour sur place. Cependant, si nous parcourons la capacité c de gauche à droite (de la plus petite à la plus grande), l’élément i risque d’être compté deux fois : nous pourrions utiliser la valeur mise à jour pour c-w[i], qui inclut déjà l’élément i. Un parcours de droite à gauche (de la plus grande à la plus petite) garantit que chaque élément est utilisé au plus une fois lors de la mise à jour d’une ligne.

En ne conservant qu’un seul tableau et en parcourant la capacité de W jusqu’à w[i] en diminuant, nous obtenons le même résultat qu’avec la table en 2D, tout en utilisant O(W) d’espace. La complexité temporelle reste O(n × W). Cette optimisation de l’espace est essentielle à retenir : les recruteurs vous demandent souvent de réduire le sac à dos en 2D à une version en 1D.

Pour déterminer quels éléments sont marqués comme selected, vous devez disposer de la table complète en 2D. Une fois celle-ci remplie, partez de dp[n][W] et remontez le parcours : si dp[i][c] != dp[i-1][c], l’élément i a été inclus — soustrayez son poids de c, puis passez à la ligne i-1. Continuez jusqu’à i = 0. L’optimisation en 1D supprime cette possibilité de reconstruction.

Considérons les éléments suivants : weights=[2,3,4,5], values=[3,4,5,6], W=8. La solution optimale consiste à prendre les éléments de poids 3 (valeur 4) et 5 (valeur 6) : poids total 8 et valeur 10. Vous pouvez aussi prendre les éléments de poids 2 et 5, pour une valeur totale de 9, ou ceux de poids 2 et 3, pour une valeur de 7. La DP trouve correctement le maximum, qui est 10. Notez que l’approche gloutonne, qui consiste à prendre l’élément ayant le rapport valeur/poids le plus élevé, choisirait d’abord l’élément de rapport 1.5 (poids 2, valeur 3), ce qui n’est pas toujours optimal.

Dans le sac à dos fractionnaire, vous pouvez prendre des fractions d’éléments. Ce problème se résout par une approche gloutonne en triant les éléments selon leur rapport valeur/poids. Dans le sac à dos 0/1, les éléments sont indivisibles : l’approche gloutonne échoue et la DP est nécessaire. Les recruteurs utilisent cette distinction pour vérifier que vous savez quand une approche gloutonne est applicable. Si l’on vous interroge sur la variante fractionnaire, mentionnez immédiatement l’approche gloutonne avec un tri ; pour la variante 0/1, utilisez la DP.

Le sac à dos 0/1 est NP-complet, et pourtant nous le résolvons en O(nW). La contradiction s’explique par le fait que O(nW) est pseudo-polynomial : W est une valeur, et non la taille de l’entrée. La représentation binaire de W nécessite O(log W) bits ; la complexité réelle est donc O(n × 2^(log W)), ce qui est exponentiel par rapport à la taille de l’entrée. Lorsque W est petit (par exemple, 10⁴), la DP est pratique ; lorsque W peut atteindre 10⁹, nous devons recourir à d’autres approches.

Si l’intervieweur impose une valeur très grande pour W (par exemple, 10⁹) mais que n est petit, la DP standard devient inutilisable. Parmi les solutions possibles : (1) la méthode de rencontre au milieu en O(2^(n/2) × n), (2) une approximation gloutonne pour la variante fractionnaire ou (3) la séparation et l’évaluation. Pour la plupart des problèmes d’entretien avec W <= 10⁵, la DP en 1D avec parcours en sens inverse est la réponse attendue.

Lorsque W est très grand mais que n est petit (par exemple, n=40), la DP standard en O(nW) est irréalisable, tandis que la force brute en 2^n est trop lente. La méthode de rencontre au milieu répartit les éléments en deux moitiés, énumère tous les sous-ensembles 2^(n/2) de chaque moitié, puis associe ces sous-ensembles de manière optimale. Triez une moitié selon le poids, puis, pour chaque sous-ensemble de l’autre moitié, utilisez une recherche binaire afin de trouver le meilleur appariement dans la limite de capacité. Cette méthode s’exécute en O(2^(n/2) × n) et reste pratique jusqu’à n=40.

Évaluez votre compréhension des notions de structures de données et d’algorithmes — préparation aux entretiens de programmation — abordées dans cette leçon.

Dans cette leçon, vous avez appris : la DP du sac à dos 0/1 utilise l’état dp[i][c], qui représente la valeur maximale obtenue avec i éléments et une capacité c, la récurrence choisit de ne pas prendre ou de prendre chaque élément, et l’optimisation de l’espace en 1D parcourt la capacité de droite à gauche afin d’éviter de compter les éléments deux fois. Ensuite, nous étudions le sac à dos non borné, où les éléments peuvent être réutilisés, et l’appliquons au rendu de monnaie II.