0/1-Knapsack: Nehmen oder ablehnen
Maximieren Sie den Wert unter einer Gewichtsgrenze
0/1-Knapsack: Nehmen oder ablehnen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die Geschichte des Rucksackproblems
Sie haben eine Tasche mit Gewichtslimit und einen Stapel von Gegenständen. Beim 0/1-Rucksackproblem lautet die Frage: Welche Gegenstände maximieren den Wert, ohne die Tasche zu überladen? 🎒
Nehmen oder liegen lassen
0/1 bedeutet, dass jeder Gegenstand entweder vollständig genommen oder vollständig ausgelassen wird. Sie können niemals nur einen Teil eines Gegenstands nehmen; jede Entscheidung lautet also Ja oder Nein.
Warum der Greedy-Ansatz scheitert
Wenn Sie zuerst den günstigsten oder wertvollsten Gegenstand nehmen, können Sie Kapazität verschwenden. Die Greedy-Abkürzung funktioniert hier nicht; stattdessen müssen Sie echte Kombinationen berücksichtigen.
Die beiden Eingaben
Sie erhalten zwei parallele Listen: ein Gewicht und einen Wert für jeden Gegenstand sowie eine Kapazität. Gegenstand i hat das Gewicht wt[i] und den Wert val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Den Zustand definieren
Sei dp[i][w] der beste Wert, den Sie mit den ersten i Gegenständen bei der Kapazität w erreichen. Den Zustand präzise zu benennen, ist der entscheidende Schritt.
Die Möglichkeit des Überspringens
Wenn Sie Gegenstand i überspringen, entspricht Ihr Wert dem bisherigen Wert: dp[i-1][w]. Die Kapazität bleibt für den Rest unverändert.
Die Möglichkeit des Nehmens
Wenn Sie Gegenstand i nehmen, addieren Sie seinen Wert und verringern die Kapazität: val[i] + dp[i-1][w - wt[i]]. Das ist nur zulässig, wenn w mindestens wt[i] beträgt.
Den besseren Zweig wählen
Die Rekurrenz behält mit max einfach die größere der beiden Möglichkeiten. Jede Zelle vertraut auf die bereits darunter berechneten Ergebnisse.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])Die Basiszeile
Mit null Gegenständen können Sie bei jeder Kapazität einen Wert von null transportieren. Dieser Basisfall füllt die erste Zeile vollständig mit Nullen, auf denen Sie aufbauen.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Die Tabelle füllen
Durchlaufen Sie die Gegenstände in der äußeren und die Kapazitäten in der inneren Schleife. Jede Zelle liest nur die Zeile darüber, sodass ein einziger Durchlauf alles füllt.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Das Ergebnis ablesen
Die Zelle unten rechts, dp[n][cap], enthält den maximalen Wert für alle Gegenstände und die vollständige Kapazität. Diese eine Zelle ist Ihr endgültiges Ergebnis.
Schnelltest
Testen Sie die grundlegende Rekurrenz des 0/1-Rucksackproblems.
Zusammenfassung
Sie haben das 0/1-Rucksackproblem kennengelernt: Jeder Gegenstand wird genommen oder ausgelassen, dp[i][w] behält das bessere Ergebnis aus Überspringen und Nehmen, und dp[n][cap] ist die Antwort. 🎉
Häufig gestellte Fragen
Ist die Lektion „0/1-Knapsack: Nehmen oder ablehnen“ kostenlos?
Ja — der vollständige Text von „0/1-Knapsack: Nehmen oder ablehnen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „0/1-Knapsack: Nehmen oder ablehnen“?
Maximieren Sie den Wert unter einer Gewichtsgrenze Du übst Coding Interview Prep 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep 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 1 von 4.
Wie lange dauert die Lektion „0/1-Knapsack: Nehmen oder ablehnen“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-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
- 0/1-Knapsack: Nehmen oder ablehnen
- Knapsack mit optimiertem Speicherbedarf
- Unbeschränktes Knapsack und Münzwechsel-DP
- Teilmengensumme und Partitionierung