dynamic-programming
Münzwechsel Problem

Anzahl der Möglichkeiten, um insgesamt zu erhalten

Wie viele verschiedene Münzen können wir kombinieren, um die Summe zu erhalten? Nehmen wir an, wir haben coins = {1, 2, 3} und total = 5 , wir können die Summe auf 5 Arten erhalten:

• 1 1 1 1 1 1
• 1 1 1 2
• 1 1 3
• 1 2 2
• 2 3

Das Problem hängt eng mit dem Rucksackproblem zusammen. Der einzige Unterschied ist, dass wir unbegrenzt mit Münzen ausgestattet sind. Wir werden dynamische Programmierung verwenden, um dieses Problem zu lösen.

Wir verwenden ein 2D-Array dp [n] [total + 1], wobei n die Anzahl der verschiedenen Münzwerte ist, die wir haben. Für unser Beispiel benötigen wir dp [3] [6] . Hier bezeichnet dp [i] [j] die Anzahl der Möglichkeiten, wie wir j bekommen können, wenn wir Münzen von Münzen [0] bis zu Münzen [i] hätten . Zum Beispiel speichert dp [1] [2] , wenn wir Münzen [0] und Münzen [1] hätten , auf wie viele Arten wir 2 machen könnten. Lass uns anfangen:

Für dp [0] [0] fragen wir uns, ob wir nur 1 Münzwert hatten, das heißt Münzen [0] = 1 , auf wie viele Arten können wir 0 bekommen? Die Antwort ist ein Weg, das ist , wenn wir nicht überhaupt eine Münze nehmen. Wenn wir weitergehen, stellt dp [0] [1] dar, wenn wir nur Münzen [0] hätten . Wie viele Möglichkeiten gibt es 1 ? Die Antwort ist wieder 1 . Auf dieselbe Weise werden dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] 1 sein . Unser Array wird wie folgt aussehen:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

Für dp [1] [0] fragen wir uns, ob wir Münzen mit 2 Konfessionen hätten, das heißt, ob wir Münzen [0] = 1 und Münzen [1] = 2 hätten , auf wie viele Arten könnten wir 0 machen? Die Antwort ist 1 , was bedeutet, dass überhaupt keine Münzen genommen werden. Für dp [1] [1] wird 2 nicht zur Gesamtsumme beitragen, da die Münzen [1] = 2 größer sind als unsere aktuelle Summe. Also schließen wir 2 aus und zählen die Anzahl der Möglichkeiten, wie wir die Summe mithilfe von Münzen erhalten können [0] . Dieser Wert ist aber bereits in dp [0] [1] gespeichert! Also nehmen wir den Wert von oben. Unsere erste Formel:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

Wie viele Möglichkeiten gibt es für dp [1] [2] , 2 zu bekommen, wenn wir Münzen der Nennwerte 1 und 2 hätten ? Wir können 2 mit Münzen des Nennwerts 1 herstellen , die durch dp [0] [2] dargestellt werden. Wieder können wir 1 Nennwert 2 nehmen, der in dp [1] [2-Münzen [i]] gespeichert ist, wobei i = 1 . Warum? Es ist offensichtlich, wenn wir das nächste Beispiel betrachten. Wie viele Möglichkeiten gibt es für dp [1] [3] 3 , wenn wir Münzen der Nennwerte 1 und 2 hätten ? Wir können 3 unter Verwendung von Münzen der Stückelung 1 in 1 Art und Weise machen, die in dp gespeichert wird [0] [3]. Wenn wir nun 1 Nennwert von 2 nehmen , brauchen wir 3 - 2 = 1 , um die Summe zu erhalten. Die Anzahl der Möglichkeiten, 1 mit den Münzen der Nennwerte 1 und 2 zu erhalten, ist in dp [1] [1] gespeichert, das als dp [i] [j-coins [i]] geschrieben werden kann , wobei i = 1 ist . Deshalb haben wir den vorherigen Wert so geschrieben. Unsere zweite und letzte Formel lautet:

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

Dies sind die zwei erforderlichen Formeln, um das gesamte dp- Array aufzufüllen. Nach dem Auffüllen sieht das Array folgendermaßen aus:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [5] enthält unsere gewünschte Antwort. Der Algorithmus:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

Die zeitliche Komplexität dieses Algorithmus ist O(n * total) , wobei n die Anzahl der Münzwerte ist, die wir haben.

Mindestanzahl an Münzen, um die Summe zu erhalten

Wie viele Münzen müssen wir bei Münzen mit unterschiedlichen Nennwerten und Gesamtmenge kombinieren, um die Summe zu erhalten, wenn wir eine minimale Anzahl von Münzen verwenden? Nehmen wir an, wir haben coins = {1, 5, 6, 8} und eine total = 11 , wir können die Summe mit 2 Münzen berechnen, also {5, 6} . Dies ist in der Tat die Mindestanzahl an Münzen, um 11 zu erhalten. Wir gehen auch davon aus, dass es unendlich viele Münzen gibt. Wir werden dynamische Programmierung verwenden, um dieses Problem zu lösen.

Wir verwenden ein 2D-Array dp [n] [total + 1], wobei n die Anzahl der verschiedenen Münzwerte ist, die wir haben. Für unser Beispiel benötigen wir dp [4] [12] . Hier bezeichnet dp [i] [j] die Mindestanzahl von Münzen, die erforderlich ist, um j zu erhalten, wenn wir Münzen von Münzen [0] bis zu Münzen [i] hatten . Zum Beispiel speichert dp [1] [2] , wenn wir Münzen [0] und Münzen [1] hätten . Wie viele Münzen können wir mindestens 2 machen. Lass uns anfangen:

Für die 0- te Spalte kann 0 zuerst gemacht werden, indem keine Münzen genommen werden. Alle Werte der 0- ten Spalte sind also 0 . Für dp [0] [1] fragen wir uns, ob wir nur 1 Münze haben, das heißt Münzen [0] = 1. Wie viele Münzen braucht man mindestens, um 1 zu bekommen? Die Antwort ist 1 . Für dp [0] [2] , wenn wir nur 1 hätten , wie viele Münzen müssen mindestens 2 sein , um 2 zu erhalten. Die Antwort lautet 2 . Ähnlich ist dp [0] [3] = 3 , dp [0] [4] = 4 und so weiter. Eine Sache , hier zu erwähnen ist , dass, wenn wir nicht eine Münze der Stückelung 1, hatte es könnte einige Fälle, in denen die Summe kann nicht nur unter Verwendung von 1 Münze erreicht werden. Der Einfachheit halber nehmen wir 1 in unserem Beispiel. Nach der ersten Iteration sieht unser dp- Array folgendermaßen aus:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Weiter für dp [1] [1] fragen wir uns, ob wir Münzen [0] = 1 und Münzen [1] = 5 hätten . Wie viele Münzen braucht man mindestens, um 1 zu bekommen? Da die Münzen [1] über unserer aktuellen Summe liegen, hat dies keinen Einfluss auf unsere Berechnung. Wir müssen Münzen ausschließen [5] und nur 1 mit Münzen [0] erhalten . Dieser Wert wird in dp [0] [1] gespeichert. Also nehmen wir den Wert von oben. Unsere erste Formel lautet:

if coins[i] > j
    dp[i][j] := dp[i-1][j]

Diese Bedingung ist wahr, bis unsere Summe 5 in dp [1] [5] ist. In diesem Fall können wir 5 auf zwei Arten machen:

• Wir nehmen 5 Stückelungen von Münzen [0] , die auf dp [0] [5] (von oben) gespeichert sind.
• Wir nehmen 1 Stück von Münzen [1] und ( 5 - 5 ) = 0 Stück von Münzen [0] .

Wir werden das Minimum von diesen beiden wählen. Also dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Warum haben wir hier 0 Stückelungen von Münzen erwähnt?

Für dp [1] [6] können wir 6 auf zwei Arten machen:

• Wir nehmen 6 Münzwerte [0] , die oben gespeichert sind.
• Wir können 1 Bewertung von 5 annehmen, wir brauchen 6 - 5 = 1 , um die Summe zu erhalten. Die Mindestanzahl von Wegen, um 1 mit den Münzen der Nennwerte 1 und 5 zu erhalten, wird in dp [1] [1] gespeichert, das als dp [i] [j-coins [i]] geschrieben werden kann , wobei i = 1 ist . Deshalb haben wir den vorherigen Wert so geschrieben.

Wir nehmen das Minimum dieser zwei Wege. Unsere zweite Formel lautet also:

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

Mit diesen beiden Formeln können wir die ganze Tabelle füllen. Unser Endergebnis wird sein:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Unser gewünschtes Ergebnis wird in dp [3] [11] gespeichert. Das Verfahren wird sein:

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

Die Laufzeitkomplexität dieses Algorithmus ist: O (n * total) wobei n die Anzahl der Münzen ist.

Um die benötigten Münzen zu drucken, müssen wir Folgendes prüfen:

• Wenn der Wert von oben kam, ist die aktuelle Münze nicht enthalten.
• Wenn der Wert von links kam, ist die aktuelle Münze enthalten.

Der Algorithmus wäre:

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

Für unser Beispiel lautet die Richtung:

Die Werte werden 6 , 5 sein .