Sac à Dos Fractionnaire
Algorithmique classique
Enonce
Résoudre le problème du sac à dos fractionnaire : on peut prendre une fraction d'un objet. Maximiser la valeur totale sans dépasser la capacite.
Signature attendue
def sac_a_dos_frac(poids: list, valeurs: list, capacite: float) -> float:Exemples
sac_a_dos_frac([10, 20, 30], [60, 100, 120], 50)→240.0sac_a_dos_frac([5, 10], [50, 60], 10)→80.0
📖 Rappel de cours
On trie par rapport valeur sur poids décroissant, on remplit avec les meilleurs objets, et on complète avec une fraction du suivant.
⚠ Le piège : Ici le glouton est optimal, contrairement au sac à dos 0-1 — précisément parce qu'on peut couper un objet. C'est la seule différence, et elle change tout.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Composantes Connexes
- Rendu de Monnaie Glouton
- Sélection d'Activités
- Couverture d'Intervalles
- Codage de Huffman Simplifié
- Compter les Bits à 1
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.