Eine DP-Aufgabe erkennen in Java

Problem

Welche Anfragen soll der Transporter annehmen?

Du hast einen Mietwagen. Für morgen gibt es sechs Transportanfragen, jede mit Start, Ende und Preis. Der Transporter kann nur an einem Ort sein, also können zwei Anfragen, die sich überschneiden, nicht beide angenommen werden. Welche nimmst du an, um am meisten zu verdienen?

Das Erste, was einem einfällt, ist eine gierige Regel: erst die teuerste Anfrage, dann die nächste, die nicht stört. Oder: die, die am frühesten endet, damit mehr Zeit bleibt:

static List<Job> greedy(Job[] jobs, Comparator<Job> rule) {
    Job[] queue = jobs.clone();
    Arrays.sort(queue, rule);
    List<Job> taken = new ArrayList<>();
    for (Job job : queue) {
        boolean free = true;
        for (Job t : taken) {
            if (job.start() < t.end() && t.start() < job.end()) free = false;
        }
        if (free) taken.add(job);
    }
    return taken;
}

static void show(String rule, List<Job> taken) {
    int sum = taken.stream().mapToInt(Job::pay).sum();
    List<String> names = taken.stream().map(Job::name).toList();
    System.out.println(rule + ": " + String.join(", ", names) + " = " + sum + " €");
}

show("Die teuersten zuerst", greedy(jobs, Comparator.comparingInt(Job::pay).reversed()));
show("Das früheste Ende zuerst", greedy(jobs, Comparator.comparingInt(Job::end)));

Die teuersten zuerst: Flughafen, Sofa = 180 €
Das früheste Ende zuerst: Markt, Büro, Reparatur = 170 €

Beide Regeln lassen Geld liegen: Es gibt einen Plan, der mehr wert ist. Alle 2⁶ = 64 Teilmengen auszuprobieren funktioniert hier, aber bei 60 Anfragen sind es über eine Trillion. Die Aufgabe ist von derselben Art wie der Rucksack und Diff. Wie erkennst du das selbst, und wie baust du die Lösung?

Die Idee

Die Merkmale

Eine Aufgabe ist etwas für die dynamische Programmierung, wenn sie drei Dinge hat:

Die Frage betrifft das Beste oder die Anzahl. „Am meisten“, „am wenigsten“, „auf wie viele Arten“, „geht es überhaupt“. Fragt sie nur „finde das Element“ oder „sortiere“, gibt es nichts zu wählen.
Optimale Teilstruktur. Die beste Lösung des Ganzen wird aus den besten Lösungen kleinerer Teile gebaut. Beim Transporter: Ist die letzte Anfrage im besten Plan, ist der Rest der beste Plan der Anfragen, die vor ihr enden.
Überlappende Teilprobleme. Dieselben kleineren Teile werden oft gefragt, wie beim naiven Fibonacci. Beim Transporter beginnen „Reparatur“ und „Flughafen“ beide um 15:00 Uhr und fragen dasselbe: das Meiste aus den Anfragen, die um 15:00 Uhr enden.

Sind alle drei da, wird die Antwort für jeden kleinen Teil einmal berechnet und aufgeschrieben.

Die Idee

Das Rezept in fünf Schritten

Zustand. Was eine Zelle ist: „best[i] ist das meiste Geld aus den ersten i Anfragen, nach dem Ende sortiert“. Ein guter Zustand beschreibt die kleine Aufgabe mit ein oder zwei Zahlen.
Übergang. Wie die Zelle aus kleineren berechnet wird. Für Anfrage i gibt es zwei Wahlen: sie auslassen (best[i − 1]) oder sie nehmen (ihr Preis + best[p], wobei p die Anzahl der Anfragen ist, die bis zu ihrem Start enden). best[i] ist die größere.
Basis. Die Zellen, die von nichts abhängen: best[0] = 0, keine Anfragen, kein Geld.
Reihenfolge. In welcher Reihenfolge gefüllt wird, damit das Nötige schon fertig ist: von links nach rechts, weil i nur i − 1 benutzt und p < i ist.
Antwort. Welche Zelle die Antwort ist: best[n]. Willst du auch wissen, welche Anfragen, gehst du an den Entscheidungen entlang zurück, wie der Weg zurück im Diff.

Das Sortieren nach dem Ende gehört zum Zustand: So sind die mit der i-ten verträglichen Anfragen genau die ersten p, und „das Beste davon“ ist eine Zelle.

Genauer, für Neugierige

Dasselbe Rezept funktioniert auch von oben nach unten: eine Funktion best(i), die best(i − 1) und best(p) aufruft und das Ergebnis merkt (siehe Memoization). Die Tabelle von unten nach oben und die Rekursion mit Speicher berechnen dieselben Zellen. Die Rekursion liegt näher an den Worten des Übergangs, die Tabelle hat keinen tiefen Stapel.

In Java ist Memoization eine Map<Integer, Integer> oder ein Array mit -1 für „noch nicht berechnet“. Tiefe Rekursion kann StackOverflowError auslösen, deshalb ist bei langen Folgen die Tabelle sicherer.

p lässt sich mit binärer Suche auf den Enden finden, weil sie sortiert sind: Dann ist das Ganze O(n log n). Die Schleife in der Lektion ist O(n) pro Anfrage, insgesamt O(n²), und für sechs Anfragen reicht das völlig.

Sieh es dir an

Das Rezept im Code

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[p];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Arrays.sort sortiert das Array an Ort und Stelle, und Comparator.comparingInt(Job::end) sagt, wonach. Die Schleife für p hält spätestens bei der i-ten Anfrage selbst an, weil sie nach ihrem Start endet.

Job[] jobs = {
    new Job("Sofa", 9, 12, 80),
    new Job("Flughafen", 15, 20, 100),
    new Job("Markt", 8, 10, 60),
    new Job("Lager", 12, 17, 30),
    new Job("Büro", 11, 13, 60),
    new Job("Reparatur", 15, 19, 50),
};
System.out.println("Höchstens: " + bestPay(jobs) + " €");

Höchstens: 220 €

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[p];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Schritt für Schritt, in Worten

Sechs Anfragen für einen Transporter. Zustand: Sortiere sie nach dem Ende; best[i] ist das meiste Geld aus den ersten i.
Basis: best[0] = 0, keine Anfragen, kein Geld. Reihenfolge: von links nach rechts, jede Zelle braucht nur Zellen links von ihr.
Anfrage 1, Markt 8–10 Uhr, 60 €: keine Anfrage endet vor ihrem Start, p = 0. Auslassen: best[0] = 0. Nehmen: 60 + best[0] = 60. Besser, sie zu nehmen: best[1] = 60.
Anfrage 2, Sofa 9–12 Uhr, 80 €: keine Anfrage endet vor ihrem Start, p = 0. Auslassen: best[1] = 60. Nehmen: 80 + best[0] = 80. Besser, sie zu nehmen: best[2] = 80.
Anfrage 3, Büro 11–13 Uhr, 60 €: eine endet bis 11:00 Uhr, p = 1. Auslassen: best[2] = 80. Nehmen: 60 + best[1] = 120. Besser, sie zu nehmen: best[3] = 120.
Anfrage 4, Lager 12–17 Uhr, 30 €: 2 enden bis 12:00 Uhr, p = 2. Auslassen: best[3] = 120. Nehmen: 30 + best[2] = 110. Besser, sie auszulassen: best[4] = 120.
Anfrage 5, Reparatur 15–19 Uhr, 50 €: 3 enden bis 15:00 Uhr, p = 3. Auslassen: best[4] = 120. Nehmen: 50 + best[3] = 170. Besser, sie zu nehmen: best[5] = 170.
Anfrage 6, Flughafen 15–20 Uhr, 100 €: 3 enden bis 15:00 Uhr, p = 3. Auslassen: best[5] = 170. Nehmen: 100 + best[3] = 220. Besser, sie zu nehmen: best[6] = 220.
Antwort: best[6] = 220 €. Entlang „nehmen“ zurück ergeben sich die Anfragen: Markt, Büro, Flughafen.

220 € aus Markt, Büro und Flughafen: mehr als sowohl „die teuerste zuerst“ als auch „das früheste Ende zuerst“.

Probier es aus

Finde den Fehler

Ein Kollege hat den Übergang kopiert. Das Programm sagt:

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[i - 1];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Job[] jobs = {
    new Job("Sofa", 9, 12, 80),
    new Job("Flughafen", 15, 20, 100),
    new Job("Markt", 8, 10, 60),
    new Job("Lager", 12, 17, 30),
    new Job("Büro", 11, 13, 60),
    new Job("Reparatur", 15, 19, 50),
};
System.out.println("Höchstens: " + bestPay(jobs) + " €");

Höchstens: 380 €

Das ist unmöglich: Alle sechs Anfragen zusammen passen nicht in einen Transporter. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Eine zweite Aufgabe: Parken entlang der Strecke

Ein Lastwagen fährt vom Lager zum letzten Parkplatz an der Autobahn. Der Fahrer muss Pausen machen: Von einem Stopp erreicht er höchstens den nächsten oder den übernächsten. Jeder Stopp hat eine Gebühr. Wie wenig zahlt er, wenn er auch am letzten hält?

Die Merkmale: „wie wenig“, und der günstigste Weg zu Stopp i führt über den günstigsten Weg zu i − 1 oder zu i − 2. Das Rezept:

Zustand: cost[i] ist das Wenigste, das bis Stopp i gezahlt wird, mit Halt dort.
Übergang: cost[i] = die Gebühr von i + min(cost[i − 1], cost[i − 2]).
Basis: Vom Lager erreicht er Stopp 0 oder fährt direkt zu Stopp 1, also sind cost[0] und cost[1] einfach ihre Gebühren.
Reihenfolge: von links nach rechts.
Antwort: die Kosten des letzten Stopps.

static int minFees(int[] fee) {
    int n = fee.length;
    int[] cost = new int[n];
    cost[0] = fee[0];
    cost[1] = fee[1];
    for (int i = 2; i < n; i++) {
        cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
    }
    return cost[n - 1];
}

int[] parking = {4, 9, 3, 12, 5, 2, 10, 6};
System.out.println("Mindestens: " + minFees(parking) + " €");

Mindestens: 20 €

Probier es aus

Sag die Ausgabe voraus

Vier Parkstopps mit Gebühren von 5 €, 1 €, 4 € und 2 €:

static int minFees(int[] fee) {
    int n = fee.length;
    int[] cost = new int[n];
    cost[0] = fee[0];
    cost[1] = fee[1];
    for (int i = 2; i < n; i++) {
        cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
    }
    return cost[n - 1];
}

int[] parking = {5, 1, 4, 2};
System.out.println("Mindestens: " + minFees(parking) + " €");

Antwort

Mindestens: 12 €

Mindestens: 3 €

Mindestens: 8 €

Die Idee

Eine dritte Aufgabe: Text ohne Leerzeichen

Kunden tippen „sommerschlussverkauf“ ohne Leerzeichen ins Suchfeld, wie bei einem Hashtag. Lässt sich der Text in Wörter des Wörterbuchs zerlegen?

Das Merkmal ist „ist es möglich“: ja oder nein. Das Rezept:

Zustand: ok[i] heißt „die ersten i Buchstaben lassen sich in Wörter zerlegen“.
Übergang: ok[i] ist wahr, wenn es ein j < i mit ok[j] gibt und die Buchstaben von j bis i ein Wort des Wörterbuchs sind.
Basis: ok[0] ist wahr: Der leere Anfang lässt sich immer zerlegen.
Reihenfolge: i wächst.
Antwort: ok[n].

static boolean canSplit(String text, Set<String> words) {
    int n = text.length();
    boolean[] ok = new boolean[n + 1];
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i && !ok[i]; j++) {
            ok[i] = ok[j] && words.contains(text.substring(j, i));
        }
    }
    return ok[n];
}

Set<String> words = Set.of(
    "sommer", "som", "schluss", "verkauf", "schuh", "schuhe", "für", "kinder", "kind");
for (String text : List.of("sommerschlussverkauf", "schuhefürkinder", "schuhefürbabys")) {
    System.out.println(text + ": " + (canSplit(text, words) ? "ja" : "nein"));
}

sommerschlussverkauf: ja
schuhefürkinder: ja
schuhefürbabys: nein

Genauer, für Neugierige

Für jedes i probiert die Schleife bis zu i Stellen für j aus, und jedes Stück wird ausgeschnitten und im Wörterbuch nachgeschlagen. Das Ausschneiden kopiert die Buchstaben (substring erzeugt einen neuen String), also ist das Ganze bei einem Text aus n Buchstaben bis zu O(n³). Hat das längste Wort des Wörterbuchs L Buchstaben, muss j nur zwischen i − L und i liegen, und die Zeit sinkt auf O(n · L²). Echte Suchmaschinen benutzen einen Trie der Wörterbuchwörter: Sie gehen die Buchstaben ab j entlang und halten an, sobald der Trie endet.

Probier es aus

Ergänze den Übergang

static boolean canSplit(String text, Set<String> words) {
    int n = text.length();
    boolean[] ok = new boolean[n + 1];
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i && !ok[i]; j++) {
            ok[i] = ;
        }
    }
    return ok[n];
}

Die Idee

Sieht nach DP aus, ist es aber nicht

Nicht jede „am meisten“-Aufgabe braucht eine Tabelle.

Gierig reicht manchmal. Zahlen alle Anfragen des Transporters dasselbe, wird die Frage zu „wie viele Anfragen höchstens“, und die Regel „das früheste Ende zuerst“ liefert genau das Beste, in O(n log n) und ohne Tabelle. Wann gierig nachweislich richtig ist und warum, steht im nächsten Modul. Das Merkmal: In jedem Schritt ist eine Wahl immer mindestens so gut wie jede andere.
Der Graph hat keine Reihenfolge. Der kürzeste Weg in einer Stadt sieht nach DP aus: Die Distanz zu einer Kreuzung wird aus den Distanzen zu ihren Nachbarn gebaut. Aber die Straßen bilden Schleifen, und „bis A“ hängt von „bis B“ ab, während „bis B“ von „bis A“ abhängt. Es gibt keine Reihenfolge, in der man die Tabelle von links nach rechts füllen könnte. Deshalb ist es dort Dijkstra: Er findet die Reihenfolge unterwegs.
Keine Überlappung. Wiederholen sich die Teilprobleme nicht, wie beim Mergesort, spart das Merken nichts. Das ist „Teile und herrsche“.

Der Test ist Schritt 4 des Rezepts: Kannst du nicht sagen, in welcher Reihenfolge zu füllen ist, geht es wahrscheinlich um einen Graphen.

Übung

Die Werbetafeln

Löse die Aufgabe in deinem Editor.

Werbetafeln. Am Boulevard stehen sieben Werbetafeln, ab 1 nummeriert, mit einer Monatsmiete von 120 €, 90 €, 60 €, 150 €, 80 €, 40 € und 130 €. Zwei benachbarte Tafeln verdecken sich, also können nicht beide vermietet werden. Schreibe die Lösung nach dem Rezept: Gib die größte Miete aus und welche Tafeln vermietet werden:

Höchstens: 400 €
Werbetafeln: 1, 4, 7

Tipp: Der Zustand ist „das Meiste aus den ersten i Tafeln“, und der Übergang ist dieselbe Wahl wie beim Transporter: Tafel i auslassen oder sie zusammen mit dem Besten bis i − 2 nehmen.

Weitere Aufgaben

Auf wie viele Arten. Auf wie viele Arten kann der Lastwagen den letzten Parkstopp erreichen (ein oder zwei Stopps auf einmal)? Nur der Übergang ändert sich: eine Summe statt eines Minimums.
Die Zerlegung mit Namen. Gib auch die Wörter von „sommerschlussverkauf“ aus: Merke dir für jedes ok[i], woher es kam.
Die Anfragen mit Namen. Lass bestPay auch zurückgeben, welche Anfragen anzunehmen sind: Geh von best[n] zurück, wie in der Szene.

Test

Teste dich

1. Welche Frage ist am ehesten eine DP-Aufgabe?Sortiere die Produkte nach PreisWie wenige Münzen zu 1, 3 und 4 Cent ergeben 6 Cent?Gibt es in der Liste eine Bestellung mit der Nummer 1042?

2. In der Aufgabe mit dem Transporter sind die Anfragen nach dem Ende sortiert. Warum?Ohne Sortieren lässt sich das Programm nicht kompilierenWeil die gierige Regel es auch tutDann sind die Anfragen, die vor der i-ten enden, die ersten der Reihe: best[p] deckt sie ab

3. Was ist die Basis für den Text ohne Leerzeichen?ok[0] = true: Der leere Text lässt sich immer zerlegenok[n] = trueok[0] = false

4. Warum wird der kürzeste Weg in der Stadt mit Dijkstra nicht als Tabelle von links nach rechts geschrieben?Die Straßen bilden Schleifen: Es gibt keine Reihenfolge, in der jede Zelle nur von fertigen Zellen abhängtWeil die Tabelle zu groß wäreWeil Dijkstra nicht den kürzesten sucht

5. Übersiehst du etwas, wenn der Übergang take = pay + best[i − 1] ist?Ja: Du verlierst die Basis best[0]Ja: Du kannst eine Anfrage nehmen, die sich mit einer schon genommenen überschneidetNein, es ist nur langsamer

Eine DP-Aufgabe erkennen

Cookies