Algorithmen und Datenstrukturen

Coin Change (Münzwechselproblem) – die Anzahl möglicher Varianten

Angenommen, wir haben ein Geldsystem mit n Münzen, wobei jede Münze einen positiven Wert besitzt: . Wir sollen ermitteln, auf wie viele verschiedene Arten man einen Gesamtbetrag von x mithilfe dieser Münzen erreichen kann.
Ein Beispiel: Wenn die Münzwerte sind und wir eine Summe von 5 bilden möchten, gibt es insgesamt 4 verschiedene Möglichkeiten: 5, 1 + 2 + 2, 1 + 1 + 1 + 2 und 1 + 1 + 1 + 1 + 1. Im Gegensatz zur Combination Sum (Kombinationssumme) spielt hier die Reihenfolge der Münzen keine Rolle – wir betrachten nur die Multimenge der verwendeten Münzen.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen n (1 ≤ n ≤ 100) und x (1 ≤ x ≤ ).
Die nächste Zeile enthält n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ).

Ausgabe

Das Programm gibt die Anzahl möglicher Varianten aus, um x mit den gegebenen Münzen zu bilden. Da das Ergebnis sehr groß werden kann, soll es modulo ausgegeben werden.

Beispiele

Input
Output
3 5 1 2 5
4
3 9 2 3 5
3

Erklärung

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2 und 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

Tutorial

Beachten Sie, dass wir zunächst versucht sein könnten, eine Zustandsvariable d[s] zu definieren, in der d[s] die Anzahl verschiedener Möglichkeiten repräsentiert, die Summe s mithilfe der Münzen zu bilden. Allerdings träte dabei ein Problem mit mehrfacher Zählung auf, da dieselbe Münzmenge in unterschiedlichen Anordnungen mehrfach gezählt würde. So würde beispielsweise das Set 1 + 2 + 2 eigentlich nur einmal vorkommen, aber fälschlicherweise dreimal gezählt werden (1 + 2 + 2, 2 + 1 + 2 und 2 + 2 + 1).
Um dieses Problem zu lösen, berücksichtigen wir bei der Berechnung den Index der Münze ci (aus dem Array c), den wir bis dahin verwenden durften. Damit erlauben wir uns, die Münze ci gar nicht oder auch mehrmals zu nutzen. Der Zustand d[s][ci] gibt also die Anzahl der Möglichkeiten an, die Summe s mit allen Münzen bis zum Index ci zu erreichen.
 
Es gibt zwei Übergänge, die uns von vorigen Zuständen zu d[s][ci] führen (der aktuelle Münzindex ist ci, der Münzwert ist val):
  1. Wir verwenden die Münze ci nicht → d[s][ci - 1]
  1. Wir verwenden die Münze ci beliebig oft (0, 1, 2, … k-mal) → d[s - val][ci]
Damit ist die Gesamtzahl der Möglichkeiten, s mit den Münzen bis ci zu bilden, die Summe beider Übergänge.
 
c = [...]
x = ...
# d mit (x+1) Zeilen und len(c) Spalten, initialisiert mit 0
d = [[0] * len(c) for _ in range(x + 1)]
Wir beginnen mit der ersten Münze und aktualisieren für alle möglichen Summen s die Zustände d[s][0]. Anschließend gehen wir zur zweiten Münze über und aktualisieren alle Zustände d[s][1], dann zur dritten Münze und so weiter, bis wir die letzte Münze betrachtet haben.
Nach der Verarbeitung aller Münzen geben wir schließlich die Anzahl der Möglichkeiten aus, die Summe x zu erreichen, indem wir d[x][len(c) - 1] ausgeben:
for ci, val in enumerate(c):      # Über die Münzen nacheinander iterieren
    d[0][ci] = 1                  # Summe 0 kann immer ohne Münzen erreicht werden
    for s in range(1, x + 1):     # Über alle Summen von 1 bis x iterieren
        if ci - 1 >= 0:           # (1) Wir verwenden ci überhaupt nicht
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) Wir verwenden ci beliebig oft
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 Kann man ein eindimensionales Array für d führen?
Da wir die Münzen nacheinander verarbeiten, können wir die bereits berechneten Zustände für Münze ci - 2 und älter verwerfen. In jeder Iteration interessieren uns nur die Zustände der aktuellen Münze ci und der vorigen Münze ci - 1. Deshalb kann man den Zustand der vorherigen Münze in einem Array und den Zustand der aktuellen Münze in einem anderen Array aufbewahren.
😎 Gibt es eine Möglichkeit, überhaupt kein zusätzliches Array zu verwenden und nur ein eindimensionales d zu nutzen?
Man kann sehen, dass die einzige Operation aus dem Zustand der vorherigen Münze die Hinzunahme von prev[s] zu d[s] ist. Daher können wir darauf verzichten, dieses vorherige Array explizit zu speichern:
# d mit x+1 Elementen initialisieren
d = [1] + [0] * x                 # Summe 0 kann ohne Münzen erreicht werden

for ci, val in enumerate(c):      # Münzen nacheinander durchgehen
    for s in range(1, x + 1):     # Über alle Summen von 1 bis x iterieren
        if s - val >= 0:          # (2) Münze ci beliebig oft nutzen
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue