Fractional Knapsack nach Verhältnis
Nehmen Sie zuerst den höchsten Wert pro Gewicht
Fractional Knapsack nach Verhältnis ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Das Rucksackproblem
Sie haben Gegenstände mit einem Wert und einem Gewicht sowie eine Tasche mit begrenzter Kapazität. Das Ziel ist, den größtmöglichen Gesamtwert zu transportieren. 🎒
Fractional bedeutet teilbar
Bei der fractional-Variante dürfen Sie einen Teil eines Gegenstands nehmen, etwa einen halben Sack Getreide. Diese Freiheit ermöglicht es greedy, hier die optimale Lösung zu finden.
Wert pro Gewicht
Die entscheidende Kennzahl ist das Verhältnis von Wert zu Gewicht jedes Gegenstands. Ein hohes Verhältnis bedeutet, dass auf sehr wenig Platz viel Wert untergebracht ist.
ratio = value / weightNach dem besten Verhältnis sortieren
Sortieren Sie die Gegenstände nach ihrem Wert-pro-Gewicht-Verhältnis, beginnend mit dem höchsten. Der greedy-Ansatz nimmt immer zuerst den verfügbaren Gegenstand mit der höchsten Wertdichte.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Ganze Gegenstände nehmen, solange sie passen
Durchlaufen Sie die sortierte Liste und nehmen Sie jeden Gegenstand vollständig, solange er in die verbleibende Kapazität passt. Addieren Sie seinen vollständigen Wert zur Gesamtsumme.
if weight <= cap:
total += value
cap -= weightDie letzte Lücke füllen
Wenn ein Gegenstand zu groß ist, nehmen Sie einen Bruchteil, der den verbleibenden Platz genau ausfüllt. Danach ist die Tasche voll und Sie hören auf.
total += value * (cap / weight)Warum die Reihenfolge nach dem Verhältnis funktioniert
Jede Kapazitätseinheit sollte möglichst viel Wert enthalten. Daher muss der dichteste Gegenstand zuerst gewählt werden. Ein Austausch durch eine geringere Dichte verringert den Wert.
Das 0/1-Rucksackproblem ist anders
Wenn Gegenstände nicht geteilt werden können, funktioniert die Greedy-Strategie nach dem Verhältnis nicht. Für die 0/1-Variante benötigen Sie dynamische Programmierung statt dieser einfachen Sortierung.
Die Laufzeit
Das Sortieren nach dem Verhältnis kostet O(n log n), und die Füllschleife ist linear. Das ist für typische Zeitlimits bei Wettbewerben schnell genug.
Achten Sie auf den letzten Bruch
Verwenden Sie für den Teil eines Gegenstands Gleitkommazahlen oder exakte rationale Zahlen. Wenn Sie zu früh abschneiden, kann Wert verloren gehen und die Antwort falsch werden.
Wo es zum Einsatz kommt
Denken Sie an das Beladen von Fracht, das Mischen von Brennstoffen oder das Aufteilen von Ressourcen. Sobald Teile teilbar sind, ist Greedy nach dem Verhältnis Ihr Werkzeug.
Schnelltest
Sie füllen eine Tasche im fraktionalen Rucksackproblem.
Zusammenfassung
Sortieren Sie die Gegenstände nach Wert pro Gewichtseinheit, nehmen Sie passende Gegenstände vollständig und füllen Sie die Tasche anschließend mit einem Bruchteil auf. Diese Greedy-Strategie ist nur dann optimal, wenn Gegenstände geteilt werden können. 🚀
Häufig gestellte Fragen
Ist die Lektion „Fractional Knapsack nach Verhältnis“ kostenlos?
Ja — der vollständige Text von „Fractional Knapsack nach Verhältnis“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Fractional Knapsack nach Verhältnis“?
Nehmen Sie zuerst den höchsten Wert pro Gewicht Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Fractional Knapsack nach Verhältnis“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Die Greedy-Denkweise
- Aktivitätsauswahl nach frühestem Ende
- Fractional Knapsack nach Verhältnis
- Erkennen, wann Greedy scheitert