Dynamische Programmierung und Greedy

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Dynamische Programmierung und Greedy zerlegen große Probleme in kleinere Entscheidungen, gehen jedoch unterschiedlich mit Entscheidungen um.

Dynamic Programming

Es wird verwendet, wenn dasselbe kleine Problem wiederholt wird und mit der optimalen Lösung des kleinen Problems die optimale Lösung für das große Problem erstellt werden kann.

int Fibonacci(int N)
{
    if (N <= 1)
    {
        return N;
    }

    std::vector<int> DP(N + 1, 0);
    DP[1] = 1;

    for (int i = 2; i <= N; ++i)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }

    return DP[N];
}

Da die berechneten Ergebnisse gespeichert werden, wird dasselbe rekursive Problem nicht wiederholt. Der Schlüssel liegt darin, Zustandsdefinitionen und Zündausdrücke richtig festzulegen.

Greedy

Treffen Sie die Wahl, die Ihnen im gegenwärtigen Moment am besten erscheint, und kehren Sie nicht zu Ihrer vorherigen Wahl zurück.

Wie beim Aktivitätsauswahlproblem gibt es Probleme, bei denen die optimale Lösung durch kontinuierliche Auswahl der Aufgabe mit der schnellsten Abschlusszeit erreicht wird. Bei dem Wechselgeldproblem, bei dem die Münzeinheiten willkürlich vergeben werden, ist es jedoch möglicherweise nicht optimal, zuerst die größte Münze auszuwählen.

Münzen: 1, 3, 4
Anzahl: 6

Gierig: 4 + 1 + 1 = 3
Optimale Lösung: 3 + 3 = 2

Greedy ist schnell und benötigt wenig Speicher, erfordert jedoch den Nachweis, dass die lokale optimale Auswahl zu einer globalen optimalen Lösung führt. Wenn Sie sich für Greedy entscheiden, nur weil einige Beispiele richtig sind, wird es bei den Gegenbeispielen scheitern.