55. Exemple DP 3 : Problème du Sac à Dos (Introduction 0/1)

Le Problème du Sac à Dos 0/1 (0/1 Knapsack Problem)

Vous avez un sac à dos (knapsack) avec une capacité de poids maximale W. Vous disposez d'un ensemble de N objets, chacun avec un poids spécifique et une valeur spécifique. Vous devez décider, pour chaque objet, de le prendre (1) ou de le laisser (0). Le but est de maximiser la valeur totale sans dépasser la capacité W.

Pourquoi la DP ?

Ce problème présente à la fois une Structure Optimale (la meilleure solution pour une capacité w repose sur la meilleure solution pour des capacités inférieures à w) et des Sous-problèmes Chevauchants.

Définition de l'État DP

Nous définissons un tableau DP 2D : DP[i][w] = valeur maximale réalisable en utilisant les i premiers objets avec une capacité de sac à dos de w.

Pour chaque objet i et capacité w, nous décidons :

1. Ne pas inclure l'objet i : DP[i-1][w]
2. Inclure l'objet i : value[i] + DP[i-1][w - weight[i]]

Nous choisissons le maximum de ces deux options. Ce remplissage itératif du tableau DP résout le problème complexe efficacement.