geordnete Ausgabe durch DP



  • Guten Tag,

    Ich habe folgendes Problem:
    Ein Text besteht aus n Wörtern mit unterschiedlichen Längen. Zwischen jedem Wort ist ein Leerzeichen. Jede Zeile ist auf M Zeichen beschränkt.
    Eine geordnete Ausgabe sei dadurch beschrieben, dass die Summe der quadrieten Restleerzeichen jeder Zeile minimal sei.

    Ich hab bis jetzt nur ein Ansatz über eine Baumstruktur die jeden möglichen Fall abdeckt. Es gibt jedoch eine bessere Methode über DP. Leider habe ich sie mir falsch notiert und sie funktioniert dadurch nicht.

    Vielleicht kann mir jemand dabei helfen.
    vielen Dank im vorraus.


  • Mod

    ComputerCarl schrieb:

    Eine geordnete Ausgabe sei dadurch beschrieben, dass die Summe der quadrieten Restleerzeichen jeder Zeile minimal sei.

    Was sind Restleerzeichen? Was wird dort quadriert, die Anzahl?



  • Sorry, war wohl doch nicht die beste Beschreibung!

    Ich mach mal ein Beispiel:

    w1 = abbab
    w2 = a
    w3 = bab
    Die Länge der Zeilen ist maximal 7.

    Die geordneste Ausgabe wäre ja:
    abbab__ -> Restleerzeichen = 2
    a_bab__ -> Restleerzeichen = 2

    Diese Restleerzeichen gehen quadriert als Optimierungskriterium ein.
    Also in diesem Fall 8. Andere Arten die Wörter aufzuschreiben, hätten
    einen größeren Fehlerwert.


Anmelden zum Antworten