Sac à dos fractionnaire par ratio
Prendre d’abord la plus grande valeur par unité de poids
Sac à dos fractionnaire par ratio est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
La configuration du sac à dos
Vous disposez d'objets ayant une valeur et un poids, ainsi que d'un sac de capacité limitée. L'objectif est de transporter la plus grande valeur totale possible. 🎒
Fractionnaire signifie divisible
Dans la version fractionnaire, vous pouvez prendre une partie d'un objet, par exemple la moitié d'un sac de céréales. C'est cette liberté qui permet à la méthode gloutonne de fonctionner ici.
Valeur par unité de poids
La mesure essentielle est le rapport entre la valeur et le poids de chaque objet. Un rapport élevé signifie qu'une grande valeur tient dans un espace très réduit.
ratio = value / weightTrier selon le meilleur rapport
sort les objets selon leur valeur par unité de poids, du rapport le plus élevé au plus faible. La stratégie gloutonne consiste à prendre sans cesse la valeur la plus dense disponible.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Prendre l'objet entier tant qu'il tient
Parcourez la liste triée et prenez chaque objet entièrement s'il tient encore dans la capacité restante. Ajoutez sa valeur totale à votre résultat.
if weight <= cap:
total += value
cap -= weightRemplir le dernier espace
Lorsqu'un objet est trop grand, prenez-en une fraction qui remplit exactement l'espace restant. Le sac est alors plein et vous vous arrêtez.
total += value * (cap / weight)Pourquoi l'ordre des rapports fonctionne
Chaque unité de capacité doit contenir la plus grande valeur possible : l'objet le plus dense doit donc être pris en premier. Remplacer cette densité par une densité moindre ne fait que réduire la valeur.
Le sac à dos 0/1 est différent
Si les objets ne peuvent pas être fractionnés, la stratégie gloutonne fondée sur le ratio échoue. La version 0/1 nécessite la programmation dynamique, et non ce simple tri.
Le temps d’exécution
Le tri par ratio coûte O(n log n), et la boucle de remplissage est linéaire. C’est largement assez rapide pour les limites habituelles des concours.
Surveillez la dernière fraction
Utilisez des nombres à virgule flottante ou des rationnels exacts pour l’objet partiel. Tronquer trop tôt peut réduire la valeur et entraîner une mauvaise réponse.
Où cette méthode s’applique
Pensez au chargement d’une cargaison, au mélange de carburants ou au partage de ressources. Dès que les éléments sont divisibles, l’algorithme glouton fondé sur le ratio est votre outil.
Vérification rapide
Vous remplissez un sac dans le problème du sac à dos fractionnaire.
Récapitulatif
Triez les objets selon leur valeur par unité de poids, prenez les objets entiers tant qu’ils tiennent, puis ajoutez une fraction pour remplir le sac. Cette stratégie gloutonne n’est optimale que lorsque les objets peuvent être fractionnés. 🚀
Questions Fréquemment Posées
La leçon « Sac à dos fractionnaire par ratio » est-elle gratuite ?
Oui — le texte complet de « Sac à dos fractionnaire par ratio » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Sac à dos fractionnaire par ratio » ?
Prendre d’abord la plus grande valeur par unité de poids Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Sac à dos fractionnaire par ratio » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- L’état d’esprit glouton
- Sélection d’activités par fin la plus précoce
- Sac à dos fractionnaire par ratio
- Repérer les échecs de l’approche gloutonne