Avancé
🧠 Fondamentaux
30 XP
0 personnes ont réussi
Problème du sac a dos (Knapsack)
Tu pars en randonnée avec un sac a dos qui ne peut porter que 50 kg. Tu as plusieurs objets, chacun avec un poids et une valeur. Tu veux emporter le maximum de valeur sans dépasser la capacite du sac.
C'est la variante 0/1 : chaque objet est pris une seule fois (tu le prends ou tu le laisses, pas de demi-portion).
On construit une matrice dp ou dp[i][w] représente la valeur maximale possible en utilisant les i premiers objets avec une capacite de w kg.
Pour chaque objet, tu as deux choix : Ne pas le prendre : dp[i][w] = dp[i-1][w] Le prendre (si le poids le permet) : dp[i][w] = dp[i-1][w - poids[i]] + valeurs[i]
Tu prends le maximum des deux.
Exemple : knapsack(50, [10, 20, 30], [60, 100, 120]) renvoie 220 (on prend les objets de poids 20 et 30, valeur 100 + 120 = 220)
Écris une fonction knapsack(capacite, poids, valeurs).