Ich habe dieses Problem kürzlich in einem dynamischen Programmiercurriculum gesehen, und ich habe wirklich keine Ahnung, wie ich den geeigneten Zustand ermitteln kann.
Sie erhalten N (1 & lt; = N & lt; = 70) Absätze und M (1 & lt; = M & lt; = N) Zahlen. Jeder Absatz i benötigt PL_i (1 & lt; = PL_i & lt; = 100) Zeilen und verweist höchstens auf eine Zahl. Jede Figur wird genau einmal referenziert (dh, keine zwei Absätze können auf dieselbe Figur verweisen, und für jede Figur gibt es einen Absatz, der darauf verweist.) Jede Figur erfordert PF_i (1 & lt; = PF_i & lt; = 100) Zeilen.
Die Aufgabe besteht darin, diese Zahlen und Absätze in der angegebenen Reihenfolge auf Papier zu verteilen, wobei ein Papier höchstens für L Zeilen passt. Kein Absatz oder eine Zahl ist zu groß, um auf ein Papier zu passen. Wenn ein Absatz x auf dem Papier x_p auf eine Figur y verweist, muss y entweder auf dem Papier
Wir müssen die minimale Anzahl von Zeilen (und somit Seiten) finden, die zugewiesen werden müssen, um alle Zahlen und Absätze zu verteilen. Jede Hilfe würde sehr geschätzt werden. Vielen Dank im Voraus!
Es gibt generell ein Problem, dass Sie die Paragrafen P und die Zahlen P order (P, F) order oder (F, P) ordering neu ordnen müssen.
Platzieren im Dokument ist (P1, F1), (P2, F2), (P3, F3), wobei jedes Tupel (P, F) in beliebiger Reihenfolge (P, F) oder (F, P) und dort sein kann sind einige Fs, die Länge 0 haben, was bedeutet, dass es kein F gibt.
Das Problem besteht darin, die Reihenfolge für jedes Paar (P, F) zu finden.
Eine Lösung zum Auffinden der geringsten Anzahl von Pailes ist die Anwendung dieser Regel
%Vor%Ok, es gibt keinen Prototyp dieser Funktion, aber für C geht es wie
%Vor%Wo pfpaires ist
%Vor%Und Sie wissen, dass Sie das Ende erreicht haben, wenn P zum Beispiel 0 ist.
Alles, was Sie tun müssen, ist eine Funktion zu erstellen, die das spezielle + Zeichen unter Berücksichtigung von Seitenumbrüchen und Todzeilen implementiert.
Dies ergibt eine O (N) -Lösung für ein Minimum an Seitenzahlen, aber nicht für die Anzahl der Zeilen, da Ihre Endbedingung 0 ist.
Wenn Sie die Anzahl der Zeilen minimieren möchten, können Sie die Bisektion verwenden, wobei Sie die Endbedingung auf etwas anderes als 0 setzen, und das gibt Ihnen
O (N * log (L)) Lösung
BEARBEITEN
Da es zwischen P und F noch ein anderes P geben kann, muss man anstelle von ((F, P), (P, F)) auch nach der leeren Seite (N) suchen, so dass die Kombos ((P, F) P, N, F), (F, P), (F, N, P)). Schlussfolgerung ist, dass Sie einen komplizierteren Algorithmus, aber die gleiche Komplexität haben. Punkt ist, dass, sobald Sie eine von 4 Ordnungen überprüfen, es nur eine einfache Möglichkeit gibt, die optimale Positionierung vorzunehmen, nur den aktuellen Status (Linien) ist ein bisschen kompliziert.
Als DP-Status für die aktuelle Seite P können Sie ein Array (der Größe L * 2) verwenden, indiziert durch die Anzahl der Zeilen, reserviert auf Seite P für Zahlen, die von Seite P + referenziert werden 1 oder (negierte) Anzahl von Zeilen, benötigt auf Seite P + 1 für Abbildungen, referenziert von Seite P.
Jedes Array-Element besteht aus zwei Werten:
Verwenden Sie dieses Array, um das Array für die nächste Seite (P + 1) zu berechnen. Fügen Sie für jedes gültige Element des Arrays P neue Absätze ( x +1, x +2, ...) zur Seite P + 1 hinzu und aktualisieren Sie die entsprechenden Elemente der Array P + 1. Während es möglich ist, platzieren Sie Zahlen, auf die in diesen Absätzen Bezug genommen wird, auf Seite P, dann auf Seite P + 1 und dann auf Seite P + 2. Überschreibt Elemente des Arrays P + 1 mit niedrigeren Werten von x mit höheren Werten.
Zeitkomplexität dieses Algorithmus ist O ( L * N ): Zeilen pro Seite mal Anzahl der Absätze. Weil die Verarbeitung jeder Seite O (Zeilen pro Seite * durchschnittliche Absätze pro Seite) ist.
Kann optimiert werden, aber es funktioniert:
%Vor%
And tests:
%pr_e%
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("20", "21", "p0" ,"22" ,"23", "p1" ,"24" ,"25", "p2")));
}
@Test
public void pageGeneration2() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(10,11));
paragraphs.add(new Paragraph(28,21));
paragraphs.add(new Paragraph(22,23));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("10", "11" ,"28", "p0" ,"21", "22" , "p1" ,"23", "p2")));
}
@Test
public void pageGeneration3() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(10,11));
paragraphs.add(new Paragraph(12,30));
paragraphs.add(new Paragraph(13,19));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("10", "11" ,"12", "13", "p0" ,"30", "19" , "p1" )));
}
@Test
public void pageGeneration4() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(10,11));
paragraphs.add(new Paragraph(30,12));
paragraphs.add(new Paragraph(13,16));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("10", "11" ,"12", "16", "p0" ,"30", "13" ,"p1" )));
}
@Test
public void pageGeneration5() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(31,32));
paragraphs.add(new Paragraph(17,21));
paragraphs.add(new Paragraph(30,35));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("31", "p0", "32", "17", "p1", "21", "p2", "30", "p3", "35", "p4")));
}
private List<String> transformToList(ArrayList<PageContent> pageContents) {
List<String> result = new ArrayList<String>();
for (int i = 0; i < pageContents.size(); i++) {
PageContent pageContent = pageContents.get(i);
if (!pageContent.texts.isEmpty()) {
for (Text text : pageContent.texts) {
result.add(String.valueOf(text.size));
}
result.add("p"+i);
}
}
return result;
}
}
Und Strukturen: Öffentliche Klasse PageContent { int LinienReserved; Sammlungstexte = new ArrayList ();
public boolean hasPicture () { für (Text: Texte) { if (Text instanceof Abbildung) { Rückkehr wahr; } } falsch zurückgeben; } } öffentliche Klasse Text { geschützte Größe; } öffentliche Klasse Figur erweitert Text { } Öffentliche Klasse Absatz erweitert Text { öffentlicher Absatz (int size, int fSIze) { this.size = Größe; this.figure = neue Figur (); this.figure.size = fSIze; } Figur Figur; }
Zuerst würde ich empfehlen, eine rekursive Methode zu erstellen.
Wählen Sie am besten aus Varianten: Beginnen Sie mit Absatz oder mit Abbildung.
Wählen Sie bei jedem Schritt das Beste aus möglichen Varianten: addieren Sie den Seitenumbruch, fügen Sie die nächste Zahl hinzu, fügen Sie den nächsten Absatz hinzu. Eine einfache Zustandsmaschine würde helfen, verbotene Varianten zu eliminieren (zum Beispiel 2 Seitenumbrüche in einer Reihe), aber es ist nicht notwendig.
Wenn rekursive Lösung geprüft wird, können Sie sie in dynamische Top-Down- oder Bottom-Up-Programmierung umwandeln, wie in den meisten algorithmischen Kursen über DP beschrieben.
Tags und Links algorithm dynamic state dynamic-programming