Sac à Dos 0/1
Algorithmique classique
Enonce
Résoudre le problème du sac à dos 0/1 : maximiser la valeur totale des objets choisis sans dépasser la capacite. Chaque objet ne peut être pris qu'une fois.
Signature attendue
def sac_a_dos(poids: list, valeurs: list, capacite: int) -> int:Exemples
sac_a_dos([2, 3, 4, 5], [3, 4, 5, 6], 5)→7sac_a_dos([1, 2, 3], [6, 10, 12], 5)→22sac_a_dos([10], [100], 5)→0
📖 Rappel de cours
Un tableau où la case (i, c) contient la meilleure valeur avec les i premiers objets et une capacité c. Pour chaque objet : le prendre s'il rentre, ou non — on garde le meilleur.
⚠ Le piège : Chaque objet est pris entièrement ou pas du tout — d'où le « 0-1 ». Le glouton par rapport valeur/poids, correct pour la version fractionnaire, échoue ici.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Flocon de Koch (coordonnées)
- Somme des Sous-ensembles
- Fibonacci par Programmation Dynamique
- Plus Longue Sous-séquence Commune (LCS)
- Distance d'Édition (Levenshtein)
- Montée d'Escalier
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.