Overview
Le problème du sac à dos 0/1 : étant donné des poids et valeurs, maximise la valeur totale sans dépasser une capacité de poids.
Analogy
Comme remplir un sac de voyage limité — chaque objet a un poids et une valeur, tu ne peux pas couper les objets.
Step-by-step
- Crée un tableau 2D dp[i][w]
- dp[i][w] = max valeur utilisant i éléments, capacité w
- Pour chaque élément, choisir de le prendre ou non
- Réponse finale : dp[n][W]
Visual
Capacité=5, éléments=[(2,3),(3,4),(4,5)]
dp[0][*]=0
dp[1][2..5]=3
dp[2][3..4]=4, dp[2][5]=7
Common mistakes
- Confondre 0/1 knapsack avec knapsack fractionnaire (glouton)
- Mauvaise indexation du tableau DP
Practice questions
- Résous le problème du sac à dos avec backtracking pour le chemin
- Optimise en utilisant un tableau 1D au lieu de 2D
Space
O(n × W) ou O(W) avec optimisation