Knapsack mit optimiertem Speicherbedarf
Reduzieren Sie zwei Dimensionen auf eine Zeile
Knapsack mit optimiertem Speicherbedarf ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 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.
Warum den Speicher optimieren
Eine vollständige Tabelle benötigt n mal cap Speicher, was bei großen Eingaben explodieren kann. Speicheroptimierung reduziert das auf eine einzige wiederverwendete Zeile.
Nur die letzte Zeile ist wichtig
Beachten Sie, dass jede Zelle nur die vorherige Zeile liest und niemals ältere Zeilen. Sie müssen daher nicht das gesamte Raster gleichzeitig speichern.
Auf ein Array reduzieren
Verwenden Sie ein dp-Array der Länge cap+1. Während Sie jeden Gegenstand verarbeiten, überschreiben Sie es an Ort und Stelle, sodass es die neue Zeile darstellt.
dp = [0] * (cap + 1)Die Falle bei der Wiederverwendung
Wenn Sie die Kapazität von links nach rechts durchlaufen, wurde dp[w - wt[i]] möglicherweise bereits für denselben Gegenstand aktualisiert. Dadurch könnten Sie Gegenstand i zweimal nehmen.
Die Kapazität rückwärts durchlaufen
Die Lösung besteht darin, die Kapazität von groß nach klein zu durchlaufen. Das rückwärts gerichtete Durchlaufen garantiert, dass dp[w - wt[i]] weiterhin den Wert des vorherigen Durchlaufs enthält.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Warum rückwärts funktioniert
Wenn Sie dp[w] berechnen, ist der kleinere Index w - wt[i] in diesem Durchlauf noch unverändert. Er entspricht daher wie vorgesehen der darüberliegenden Zeile.
Bei wt[i] früh stoppen
Kapazitäten unter wt[i] können den Gegenstand nicht aufnehmen, daher endet die Schleife bei wt[i]. Das Überspringen dieser Werte spart einige überflüssige Durchläufe.
Die vollständige Schleife
Die gesamte Lösung besteht aus zwei verschachtelten Schleifen über ein Array: außen die Gegenstände, innen die Kapazität rückwärts und schon ergibt sich das Ergebnis.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Die letzte Zelle ablesen
Nach allen Gegenständen enthält dp[cap] den maximalen Wert. Es ist dieselbe Zahl, die auch die zweidimensionale Tabelle liefern würde, aber mit deutlich weniger Speicher.
Gleiche Laufzeit, weniger Speicher
Der Algorithmus wurde nicht schneller; er benötigt weiterhin Arbeit in der Größenordnung von n mal cap. Sie haben lediglich den Speicher von quadratisch auf linear reduziert.
Wann es sich lohnt
Dieser Trick hilft Ihnen, wenn cap groß ist und das zweidimensionale Raster das Speicherlimit sprengen würde. Er gehört zu den wichtigen Standardmustern bei Programmierwettbewerben.
Schnelltest
Testen Sie die entscheidende Regel für das eindimensionale Rucksackproblem.
Zusammenfassung
Sie haben die zweidimensionale Tabelle auf ein Array reduziert und die Kapazität rückwärts durchlaufen, um korrekt zu bleiben. So tauschen Sie quadratischen Speicher gegen linearen. 🚀
Häufig gestellte Fragen
Ist die Lektion „Knapsack mit optimiertem Speicherbedarf“ kostenlos?
Ja — der vollständige Text von „Knapsack mit optimiertem Speicherbedarf“ 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 „Knapsack mit optimiertem Speicherbedarf“?
Reduzieren Sie zwei Dimensionen auf eine Zeile 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 2 von 4.
Wie lange dauert die Lektion „Knapsack mit optimiertem Speicherbedarf“?
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