Unbeschränkter Rucksack und Coin Change II
Erlauben Sie die Wiederverwendung von Elementen, indem Sie die Kapazität vorwärts durchlaufen, und lösen Sie coin-change-II (Anzahl der Möglichkeiten) sowie rod-cutting mit dieser Variante.
Unbeschränkter Rucksack und Coin Change II ist eine kostenlose DSA 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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Konzept des unbeschränkten Rucksackproblems
Beim unbeschränkten Rucksackproblem kann jeder Gegenstand beliebig oft genommen werden (anders als beim 0/1-Rucksackproblem, bei dem jeder Gegenstand höchstens einmal verwendet wird). Die Zustandsdefinition bleibt gleich — dp[c] = maximaler Wert, der mit der Kapazität c erzielt werden kann —, aber die Durchlaufrichtung ändert sich. Da Gegenstände wiederverwendbar sind, möchten wir beim Aktualisieren von dp[c] die erneute Verwendung des aktuellen Gegenstands ermöglichen. Daher durchlaufen wir die Kapazität von links nach rechts (vorwärts).
Vorwärtsdurchlauf ermöglicht Wiederverwendung
Denken Sie daran, dass wir beim 0/1-Rucksackproblem von rechts nach links durchlaufen haben, um eine Wiederverwendung zu verhindern. Beim unbeschränkten Rucksackproblem tun wir das Gegenteil: Wir durchlaufen von links nach rechts. Bei der Berechnung von dp[c] wurde dp[c-w] im aktuellen Durchlauf bereits aktualisiert — das bedeutet, dass Gegenstand i möglicherweise schon enthalten ist. Genau das ist gewünscht: Gegenstand i kann erneut zu einer Lösung hinzugefügt werden, die Gegenstand i bereits enthält.
def unbounded_knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(w, W + 1): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9Coin Change II: Möglichkeiten zählen
Bei Coin Change II lautet die Aufgabe: Zählen Sie bei gegebenen Münzwerten und einem Betrag die Anzahl der verschiedenen Möglichkeiten, diesen Betrag zu bilden (jede Münze kann unbegrenzt oft verwendet werden). Dies ist eine Variante des unbeschränkten Rucksackproblems, bei der wir statt eines Werts zu maximieren Kombinationen zählen. Definieren Sie dp[c] als die Anzahl der Möglichkeiten, den Betrag c zu bilden. Basisfall: dp[0] = 1 (eine Möglichkeit, 0 zu bilden: nichts nehmen).
Implementierung von Coin Change II
Durchlaufen Sie für jede Münze die Beträge von links nach rechts und akkumulieren Sie: dp[c] += dp[c - coin]. Der Basisfall dp[0] = 1 bildet den Ausgangspunkt für die Zählung. Beachten Sie, dass die äußere Schleife über die Münzen und die innere Schleife über die Beträge läuft — dadurch erhalten Sie auf natürliche Weise Kombinationsanzahlen (keine Permutationen), da jeder Münzwert genau einmal als äußerer Durchlauf berücksichtigt wird.
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
print(change(5, [1, 2, 5])) # 4
print(change(3, [2])) # 0
print(change(10, [10])) # 1Kombinationen vs. Permutationen
Die Reihenfolge der Schleifen ist entscheidend. Wenn wir amount in der äußeren Schleife und coin in der inneren Schleife verwenden, zählen wir Permutationen (die Reihenfolge ist relevant). Für amount=5 mit den Münzen [1,2] werden 1+2+2 und 2+1+2 getrennt gezählt. Wenn wir coin in der äußeren Schleife verwenden, zählen wir Kombinationen (die Reihenfolge ist nicht relevant): 1+2+2 und 2+1+2 sind dasselbe. Coin Change II verlangt Kombinationen, daher ist coin die äußere Schleife.
# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins: # coin outer
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in range(1, amount + 1): # amount outer
for coin in coins:
if c >= coin:
dp[c] += dp[c - coin]
return dp[amount]
print(combinations(5, [1,2,5])) # 4
print(permutations(5, [1,2,5])) # 13Das Rod-Cutting-Problem
Ein weiteres klassisches Problem des unbeschränkten Rucksackproblems: Gegeben seien ein Stab der Länge n und Preise für jede Stablänge von 1 bis n. Finden Sie den maximalen Erlös, indem Sie den Stab optimal zerteilen. Jedes Stück der Länge l kann für price[l] verkauft werden, und Stücke können wiederverwendet werden (der Stab kann in mehrere Stücke gleicher Länge zerteilt werden). Dies entspricht direkt dem unbeschränkten Rucksackproblem mit W = n, wobei die verschiedenen Schnittlängen die Gegenstände darstellen.
def rod_cutting(prices, n):
# prices[i] = price of rod of length i+1
dp = [0] * (n + 1)
for length in range(1, n + 1): # each cut length
price = prices[length - 1]
for c in range(length, n + 1):
dp[c] = max(dp[c], dp[c - length] + price)
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8)) # 22Coin Change I: Minimale Münzanzahl
Coin Change I (eine andere Aufgabe) verlangt die minimale Anzahl an Münzen, mit der ein Zielbetrag gebildet werden kann. Hier gilt dp[c] = minimale Anzahl an Münzen für den Betrag c. Rekurrenz: dp[c] = min(dp[c], dp[c - coin] + 1). Initialisieren Sie alle Einträge mit inf, außer dp[0] = 0. Auch dieses Problem ist unbeschränkt (Münzen können wiederverwendet werden), daher wird von links nach rechts durchlaufen. Geben Sie dp[amount] zurück, wenn der Wert endlich ist, andernfalls -1.
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coinChange([1,5,6,9], 11)) # 2 (5+6 or other combos)
print(coinChange([2], 3)) # -1Wichtiger Unterschied: Maximum vs. Minimum vs. Anzahl
Die drei Varianten des unbeschränkten Rucksackproblems verwenden unterschiedliche Operationen auf dp[c-coin]: Wert maximieren: dp[c] = max(dp[c], dp[c-w] + v); mit 0 initialisieren. Kosten minimieren: dp[c] = min(dp[c], dp[c-coin] + 1); mit inf initialisieren, dp[0]=0. Möglichkeiten zählen: dp[c] += dp[c-coin]; mit 0 initialisieren, dp[0]=1. Zu erkennen, welche Variante anzuwenden ist, ist bei Aufgaben in Vorstellungsgesprächen bereits die halbe Lösung.
Komplexität und Tipps für Vorstellungsgespräche
Alle Varianten des unbeschränkten Rucksackproblems benötigen O(n × W) Zeit und O(W) Speicher, wobei n die Anzahl der Gegenstandsarten und W der Zielbetrag ist. Bei Münzproblemen ist n die Anzahl der Münzwerte. Geben Sie in Vorstellungsgesprächen die Variante (Maximum/Minimum/Anzahl) an, schreiben Sie die 1D-DP auf und nennen Sie ausdrücklich, ob die äußere Schleife über coins oder amount läuft — Prüfer wissen, dass diese Unterscheidung ein tiefes Verständnis von DP testet.
Unbeschränktes Rucksackproblem vs. 0/1-Rucksackproblem erkennen
Nutzen Sie die folgenden Hinweise, um die passende Variante zu erkennen: unbegrenzte Wiederverwendung → unbeschränktes Rucksackproblem (Vorwärtsdurchlauf); jeder Gegenstand genau einmal → 0/1-Rucksackproblem (Rückwärtsdurchlauf); die Aufgabe sagt „beliebig oft“, „unbegrenzter Vorrat“ oder „Wiederverwendung erlaubt“ → unbeschränktes Rucksackproblem. Beispiele: Coin Change, Rod Cutting und Integer Break — alle unbeschränkt. Subset Sum, Partition und 0/1-Rucksackproblem — 0/1. Eine falsche Zuordnung führt zu falschen Ergebnissen, die schwer zu debuggen sind.
Integer Break und weitere Varianten
Integer Break (LeetCode 343): Teilen Sie eine ganze Zahl n in mindestens 2 positive ganze Zahlen auf, um ihr Produkt zu maximieren. Dies ist ein unbeschränktes Rucksackproblem, bei dem die „Gegenstände“ die ganzen Zahlen von 2 bis n-1 sind. Definieren Sie dp[i] = maximales Produkt von ganzen Zahlen, deren Summe i ergibt. Für jedes Element j von 2 bis i gilt dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Dies zeigt, wie sich das Muster des unbeschränkten Rucksackproblems über den Münzkontext hinaus verallgemeinern lässt.
def integerBreak(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
return dp[n]
print(integerBreak(10)) # 36 (3+3+4 = 3*3*4 = 36)Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Beim unbeschränkten Rucksackproblem wird die Kapazität von links nach rechts durchlaufen, damit Gegenstände wiederverwendet werden können, Coin Change II zählt Kombinationen, indem coin in die äußere Schleife gesetzt wird, und die drei Varianten — maximieren, minimieren, zählen — unterscheiden sich nur in der DP-Operation und der Initialisierung. Als Nächstes verwenden wir das 0/1-Rucksackproblem, um Partition Equal Subset Sum zu lösen.
Häufig gestellte Fragen
Ist die Lektion „Unbeschränkter Rucksack und Coin Change II“ kostenlos?
Ja — der vollständige Text von „Unbeschränkter Rucksack und Coin Change II“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Unbeschränkter Rucksack und Coin Change II“?
Erlauben Sie die Wiederverwendung von Elementen, indem Sie die Kapazität vorwärts durchlaufen, und lösen Sie coin-change-II (Anzahl der Möglichkeiten) sowie rod-cutting mit dieser Variante. Du übst DSA 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 DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA 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 „Unbeschränkter Rucksack und Coin Change II“?
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 DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA 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-Rucksack und Speicheroptimierung
- Unbeschränkter Rucksack und Coin Change II
- Partition Equal Subset Sum
- Zielsumme mit positiven und negativen Vorzeichen