Sac à dos (Programmation Dynamique)
Optimisation sous contrainte de poids
Enonce
Implémenter le sac à dos 0/1 par programmation dynamique. Retourner la valeur maximale.
⚠ Bonus : Retrouver la liste des objets choisis.
Signature attendue
def sac_a_dos(poids: list, valeurs: list, capacite: int) -> int:Exemple
sac_a_dos([2, 3, 4, 5], [3, 4, 5, 6], 8)→(10, [1, 3])
📖 Rappel de cours
Le problème du sac à dos 0/1 : on dispose de $n$ objets de poids $w_i$ et valeurs $v_i$. On veut maximiser la valeur totale sans dépasser la capacité $W$.
Relation de récurrence :
$dp[i][w] = \max\bigl(dp[i-1][w],\; dp[i-1][w-w_i] + v_i\bigr)$
$dp[i][w]$ = valeur maximale avec les $i$ premiers objets et capacité $w$.
Complexité : $O(n \cdot W)$ — pseudo-polynomiale.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Évaluation d'Expressions Postfixées
- Algorithme de Boyer-Moore simplifié
- Algorithme glouton : rendu de monnaie
- Plus Longue Sous-séquence Commune (LCS)
- Détection de Cycle (Floyd)
- Arbres Binaires — Parcours et Hauteur
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.