Problème du sac à dos : relation de récurrence (0/1)

1. Définition Formelle du Problème

Imaginons que vous êtes un cambrioleur (pour la bonne cause de l'algorithmique !) avec un sac à dos. Vous faites face à une série d'objets, chacun ayant une valeur et un poids. Votre sac a une capacité de poids limitée. Votre objectif est de choisir les objets à emporter pour maximiser la valeur totale, sans que le poids total ne dépasse la capacité du sac.

La contrainte "0/1" est cruciale : pour chaque objet, vous devez soit le prendre en entier (1), soit le laisser (0). Vous ne pouvez pas prendre une fraction d'un objet.

Formellement :

• Un ensemble de $n$ objets, numérotés de 1 à $n$.
• Chaque objet $i$ a un poids $p_i$ et une valeur $v_i$.
• Un sac à dos de capacité maximale en poids $W$.

Objectif : Trouver un sous-ensemble d'objets dont la somme des poids est inférieure ou égale à $W$ et dont la somme des valeurs est maximale.

Une première intuition pourrait être une approche "gourmande" : prendre en priorité les objets avec le meilleur rapport valeur/poids. Le document suivant montre rapidement pourquoi cette approche, bien qu'optimale pour le sac à dos "fractionnaire", ne l'est pas pour notre cas 0/1.

2. La Logique de la Décision : Inclure ou ne pas Inclure ?

L'échec de l'approche gourmande nous pousse à explorer toutes les solutions possibles. Pour chaque objet, nous avons deux choix : le prendre ou ne pas le prendre. Si nous avons $n$ objets, cela nous donne $2^n$ combinaisons possibles. Une approche par force brute consisterait à toutes les évaluer, ce qui est impraticable pour un $n$ un tant soit peu grand.

Cependant, cette structure de décision se prête bien à une formulation récursive. L'image suivante illustre l'arbre des décisions possibles.

3. Dérivation de la Relation de Récurrence

L'idée de la programmation dynamique est de résoudre le problème en se basant sur les solutions optimales de sous-problèmes plus simples. Définissons un sous-problème par :

• Le nombre d'objets que nous sommes autorisés à considérer (par exemple, les $i$ premiers objets).
• La capacité restante du sac ($w$).

Soit V(i, w) la valeur maximale que l'on peut obtenir en utilisant un sous-ensemble des $i$ premiers objets (de 1 à $i$) avec un sac de capacité $w$. Notre but final est de trouver V(n, W).

Pour calculer V(i, w), concentrons-nous sur le $i$-ème objet. Deux cas se présentent :

1. On décide de NE PAS inclure l'objet $i$.
   Dans ce cas, la valeur maximale que l'on peut obtenir est simplement la valeur maximale que l'on pouvait déjà obtenir avec les $i-1$ objets précédents et la même capacité $w$. La valeur est donc V(i-1, w).

2. On décide d'inclure l'objet $i$.
   Ce n'est possible que si son poids $p_i$ ne dépasse pas la capacité actuelle $w$ (c'est-à-dire si $p_i\le w$). Si on le prend, on gagne sa valeur $v_i$. Il nous reste alors à remplir le reste du sac, dont la capacité est maintenant réduite à $w-p_i$, avec les $i-1$ objets précédents. La valeur totale pour ce choix est donc v_i + V(i-1, w - p_i).

Puisque nous cherchons la valeur maximale, il nous suffit de prendre le meilleur de ces deux cas.

La vidéo suivante explique ce raisonnement de manière très didactique.

4. Formalisation et Interprétation

Synthétisons ce que nous venons de voir en une formule mathématique rigoureuse. En utilisant la notation V(i, w) :

Décortiquons chaque ligne :

• Cas de base (i=0 ou w=0): Si nous n'avons aucun objet à considérer ou si la capacité du sac est nulle, la valeur maximale est évidemment 0.
• Cas où l'objet est trop lourd (p_i > w): Si le poids de l'objet $i$ est supérieur à la capacité $w$, nous ne pouvons pas l'inclure. La seule option est de ne pas le prendre. La solution est donc la même que pour le sous-problème avec $i-1$ objets et une capacité $w$.
• Le cas général (p_i \le w): C'est le cœur de la récurrence. Nous avons le choix, et nous prenons l'option qui maximise la valeur :
  • V(i-1, w) : La valeur si l'on n'inclut pas l'objet $i$.
  • v_i + V(i-1, w - p_i) : La valeur si l'on inclut l'objet $i$.

Pour vous assurer que cette formule est bien claire, je vous invite à faire l'exercice d'interprétation proposé dans le document suivant.

Conclusion

Vous avez aujourd'hui franchi l'étape la plus importante dans la résolution du problème du sac à dos : la formulation de sa logique interne.

Points clés à retenir :

• Le problème du sac à dos 0/1 est un problème d'optimisation classique qui ne peut être résolu par une approche gourmande simple.
• Le principe de la solution repose sur une décision binaire pour chaque objet : l'inclure ou ne pas l'inclure.
• La relation de récurrence formalise cette décision en comparant la valeur optimale obtenue dans les deux cas, en se basant sur les solutions de sous-problèmes plus petits.
• La définition d'un sous-problème par (nombre d'objets considérés, capacité restante) est la clé pour établir la propriété de sous-structure optimale.

Dans notre prochaine leçon, armés de cette relation de récurrence, nous passerons à l'étape suivante, que vous connaissez bien : l'implémentation d'une solution par tabulation. Nous construirons une table 2D pour calculer V(i, w) de manière itérative et efficace, ce qui nous donnera la valeur maximale recherchée.