Unbeschränktes Knapsack und Münzwechsel-DP
Verwenden Sie Elemente beliebig oft
Unbeschränktes Knapsack und Münzwechsel-DP 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.
Unbeschränkte Gegenstände
Beim unbeschränkten Rucksackproblem kann jeder Gegenstand beliebig oft genommen werden. Denken Sie an Münzen in einem Automaten, nicht an einen festen Stapel.
Die eine winzige Änderung
Im Vergleich zu 0/1 wird nur die Schleifenrichtung umgekehrt. Bei unbeschränkten Gegenständen durchlaufen Sie die Kapazität vorwärts, also von klein nach groß.
Die Vorwärtswiederverwendung ist entscheidend
Beim Vorwärtsdurchlauf kann dp[w - coin] bereits denselben Gegenstand enthalten. Diese beabsichtigte Wiederverwendung ermöglicht es genau, ihn erneut zu nehmen.
Münzwechsel kennenlernen
Beim klassischen Münzwechselproblem wird die kleinste Anzahl von Münzen gesucht, deren Summe einen Betrag ergibt. Es handelt sich um eine unbeschränkte DP mit einem Minimum statt einem Maximum.
Den Zustand definieren
Sei dp[a] die kleinste Anzahl von Münzen, die für den Betrag a benötigt wird. Initialisieren Sie dp[0] = 0, da null Münzen den Betrag null ergeben.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Unmögliche Fälle mit Unendlich darstellen
Nicht erreichbare Beträge beginnen mit unendlich. Wenn ein Betrag am Ende unendlich bleibt, kann ihn keine Kombination von Münzen bilden.
Der Übergang
Versuchen Sie für jede Münze, jeden von ihr erreichbaren Betrag zu verbessern. Verwenden Sie eine Münze mehr als für den kleineren verbleibenden Betrag.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Warum die Vorwärtsreihenfolge
Wenn Sie die Beträge aufsteigend durchlaufen, kann dp[a - coin] diese Münze bereits enthalten. So kann eine einzelne Münze mehrfach beitragen.
Stattdessen Möglichkeiten zählen
Ersetzen Sie Minimum plus 1 durch eine Summe, um die Anzahl der Möglichkeiten für jeden Betrag zu zählen. Eine äußere Münzschleife verhindert, dass Reihenfolgen doppelt gezählt werden.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Das Ergebnis ablesen
Ihr Ergebnis steht in dp[amount]. Bei der Minimum-Variante bedeutet ein unendlicher Wert, dass sich das Ziel nicht bilden lässt.
0/1 gegenüber unbeschränkt
Merken Sie sich den einen Unterschied: Eine rückwärts durchlaufene Kapazität bedeutet, dass jeder Gegenstand einmal verwendet wird; vorwärts bedeutet unbegrenzte Verwendung. Dieselbe Tabelle, entgegengesetzter Durchlauf.
Schnelltest
Testen Sie, wodurch das Rucksackproblem unbeschränkt wird.
Zusammenfassung
Sie haben den Schleifendurchlauf für unbegrenzte Wiederverwendung auf vorwärts umgestellt und das Münzwechselproblem aufgebaut: mit Minimum für die kleinste Münzanzahl oder mit einer Summe für die Gesamtzahl der Möglichkeiten. 💰
Häufig gestellte Fragen
Ist die Lektion „Unbeschränktes Knapsack und Münzwechsel-DP“ kostenlos?
Ja — der vollständige Text von „Unbeschränktes Knapsack und Münzwechsel-DP“ 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 „Unbeschränktes Knapsack und Münzwechsel-DP“?
Verwenden Sie Elemente beliebig oft 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 „Unbeschränktes Knapsack und Münzwechsel-DP“?
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
- 0/1-Knapsack: Nehmen oder ablehnen
- Knapsack mit optimiertem Speicherbedarf
- Unbeschränktes Knapsack und Münzwechsel-DP
- Teilmengensumme und Partitionierung