Die grundlegende Idee der dynamischen Programmierung besteht darin, das Problem in mehrere Unterprobleme zu zerlegen, zunächst die Unterprobleme zu lösen und die Lösungen dieser Unterprobleme zu speichern. Wenn Sie die Lösungen dieser Unterprobleme in Zukunft bei der Lösung größerer Unterprobleme verwenden müssen, können Sie diese berechneten Lösungen direkt extrahieren, um wiederholte Operationen zu vermeiden. Die Lösung für das Speichern von Teilproblemen kann mit der Formularmethode wie dem Speichern in einem Array ausgefüllt werden.
Verwenden Sie ein praktisches Beispiel, um die algorithmische Idee der dynamischen Programmierung widerzuspiegeln - das Problem der Münzveränderung.
Frage Beschreibung:
Angenommen, es gibt mehrere Münzen und es gibt unbegrenzte Mengen. In der Mindestanzahl von Münzen, die eine bestimmte Anzahl von Änderungen ausmachen können, finden Sie bitte. Beispielsweise sind verschiedene Arten von Münzen [1, 3, 5], die minimale Anzahl von Münzen mit einem Nennwert von 2 beträgt 2 (1, 1), die minimale Anzahl von Münzen mit einem Nennwert von 4 beträgt 2 (1, 3), und die Mindestzahl der Münzen mit einem Nennwert von 11 beträgt 3 (5, 5, 1 oder 5, 3, 3).
Problemanalyse:
Angenommen, die verschiedenen Münzensätze sind Array-Münze [0, ..., N-1]. Ermitteln Sie dann die minimale Anzahl von Münzen mit dem Nennwert K, dann erfüllen die Zählfunktion und die Münzarray -Münze diesen Zustand:
count (k) = min (count (k - Münze [0]), ..., count (k - Münze [n - 1])) + 1;
Und die vorherige Formel gilt nur, wenn die Bedingung k - Münze [i]> = 0 && k - Münze [i] <k erfüllt ist.
Weil K- Coin [i] <k, bei der Berechnung der Anzahl (k), zählen Sie (i) (i <- [0, k-1]), also beinhaltet hier das Problem der Rückverfolgung.
So können wir eine Matrixmatrix [K + 1] [Münze.Length + 1] erstellen, so dass die Matrix [0] [j] alle auf 0 Werte initialisiert ist, und die minimale Anzahl von Münzen mit einem Nennwert von i in Matrix [i] [Münze.Length] speichern.
Und der spezifische Prozess ist wie folgt:
* k | Münze 1 3 5 min * 0 0 0 0 0 0 * 1 1 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2, 2, 2, 2 * ...
Schließlich lautet die spezifische Java -Code -Implementierung wie folgt:
public static int backtrackingcoin (int [] Münzen, int k) {// Backtracking -Methode + dynamische Programmierung if (Münzen == NULL || Münzen.length == 0 || k <1) {return 0; } int [] [] matrix = new int [k + 1] [Münzen.Length + 1]; für (int i = 1; i <= k; i ++) {für (int j = 0; j <coins.length; j ++) {int prek = i - Münzen [j]; if (prek> -1) {// Nur wenn es nicht weniger als 0 ist, kann PreK in der Array -Matrix existieren und die Rückverfolgung kann durchgeführt werden. matrix [i] [j] = matrix [prek] [Münzen.Length] + 1; // Der Nennwert I ist Backtracking if (Matrix [i] [Münzen.Length] == 0 || Matrix [i] [j] <matrix [i] [Münzen.Length]) {// Wenn die aktuelle Anzahl von Coins die aktuelle Anzahl von Coins ist. Matrix [i] [Münzen.length] = Matrix [i] [j]; }}} return Matrix [k] [Münzen.length]; }Der Code wurde getestet, und alle Testfälle, die in der Frage angegeben wurden, wurden vergangen!
Zusammenfassen
Der oben genannte ist der gesamte Inhalt dieses Artikels über den Implementierungscode für Münzänderungsprobleme der Dynamikprogrammierung von Java. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!