Ich will keine Lösung, nur Hilfe beim Verständnis

[Guest]

So, also ersteinmal die Aufgabenstellung:

Es geht mir hier nicht darum, dass mir jemand die Musterlösung vorlegt, es geht eher darum, dass man sagen kann: Los gehts.
Ich habe halt ein wenig Probleme mit der Aufgabenstellung...
Also mal kurz so wie ich das verstehe:
angenommen ich habe eine Folge:
int[] l= {13,2,2,3,14,7,9,10,12,8,5}
so dann sagen wir mal die max. Zeilenlänge ist 15. Dann müssten sich die Zahlen ja wie folgend anordnen:

13,2
****2****3***** // <- wobei hier schonmal ein Problem ist, dass nur 2 der 3 Abstände gleich sind
*14
****7****
***9***
***10**
**12*
*8*5

Zumindest verstehe ich das so....
Also In Java würde ich einfach Syso's machen...
Aber ich verstehe hier die Ausgabe nicht so ganz:

Das Element ij des L¨osungsvektors (i1, . . . , in) gibt dann den
Index des letzten Wortes in der j-ten Zeile an.

Was ist denn damit gemeint? Und oben, das kleine Beispiel das ich angegeben habe,
liege ich damit überhaupt richtig?
Also ich will das ganze in Java Programmieren, ist ja im Endeffekt das einzig sinnvolle um
den Algorithmus auf korrektheit zu kontrollieren. Das Problem, wie gesagt, ist halt, dass ich nicht wirklich
anfangen kann, da ich mir bei der Aufgabenstellung nicht so sicher bin. Auch diese Summen oben... irgendwie bin ich da noch etwas verwirrt.

Desweiteren, was wird denn mit dynamischer Ansatz gemeint? Normalerweise speichert man doch beim dynamischen Ansatz Werte in speziellen Datenträgern zwischen? Oder gibts da bessere Definitionen?

Würde mich über jedwede Hilfe freuen.

 

[Marco13]

****2****3***** // <- wobei hier schonmal ein Problem ist, dass nur 2 der 3 Abstände gleich sind

Es ist in der Aufgabestellung nirgendwo gesagt, dass die Abstände ganzzahlig sein müssen... Zum Anzeigen auf der Konsole wäre das natürlich notwendig, aber explizit gefordert ist es - so wie ich das interpretiere (ohne Gewähr) - anscheinend nicht.

"Das Element ij des L¨osungsvektors (i1, . . . , in) gibt dann den
Index des letzten Wortes in der j-ten Zeile an."
Was ist denn damit gemeint?

Naja, das soll ein Vektor sein, der eindeutig die Lösung beschreibt. Bei deinem Beispiel: In der ersten Zeile ist das letzte Wort das mit Index 1, in der zweiten dann das mit Index 3, ... usw. der Lösungvektor wäre dann also (1,3,4,5,6,7,8,10)

Desweiteren, was wird denn mit dynamischer Ansatz gemeint? Normalerweise speichert man doch beim dynamischen Ansatz Werte in speziellen Datenträgern zwischen?
Naja "Datenträger"... eher "Datenstukturen" .. schau auch mal hier http://de.wikipedia.org/wiki/Dynamische_Programmierung bzw. in der (deutlich!) ausführlicheren http://en.wikipedia.org/wiki/Dynamic_programming

 

[Gast]

Ach so ist das gemeint. Kommt mir zwar irgendwie immernoch komisch vor, weil was soll einem dieser Lösungsvector denn dann weiterhelfen? Aber das reicht auf jeden Fall schonmal um die Aufgabe zu bearbeiten.
Also schonmal vielen Dank an dieser Stelle.

 

[Gast]

Also ich hab das jetzt mal gelöst(?).
Ich bin mir nur jetzt wirklich nicht sicher, ob dass auch tatsächlich die korrekte Lösung auf die Fragestellung ist und ob mein Ansatz "dynamisch" ist. Laufzeit sparend ist er ja denk ich schon.
Könnte mir da vielleicht nochmal jemand eine Bestätigung oder so geben? Wäre wirklich dankbar drüber.

import java.util.ArrayList;

public class Blocksatz {

	public static void blocksatz(int maxline, int[] input){
		int currentValue=0;
		ArrayList<Integer> output= new ArrayList<Integer>();
		for(int i=0;i<input.length;i++){
			if(input[i]>maxline){
				System.err.println("Word "+ i+" of the input text is too big.");
				break;
			}
			// Hier gehts los
			else{
				if(input[i]+currentValue<=maxline){
					currentValue=input[i]+currentValue;
				}
				else{
					System.out.print(i-1+"("+input[i-1]+"),");
					output.add(input[i-1]);
					currentValue=input[i];
					
				}
			}
		}
	}
	
	public static void main(String[] args){
		int zeilenLaenge = 15;
		int[] eingabeFolge=  {13,2,2,3,14,7,9,10,12,8,5} ;
		blocksatz(zeilenLaenge,eingabeFolge);
	}
}

 

[Marco13]

Hm. Das ist ja jetzt erstmal ein trivialster Greedy-Algorithmus: Du füllst die Zeilen bis nichts mehr reinpasst, und bearbeitest dann die nächste. Damit wird nicht immer die Optimale Lösung gefunden. Der Fall, dass es vielleicht günstiger ist, ein Wort, dass eigentlich noch in die aktuelle Zeile passt, DOCH in die nächste Zeile zu packen (weil dadurch die Gesamtlösung besser wird) ist dabei nicht berücksichtigt.

Ein Besipiel (die Zahlen nicht so für bare Münze nehmen - dienen nur zur Verdeutlichung des Problems!)

Wortlängen: 2, 2, 2, 2, 6, 6
Zeilenlänge: 8


Dein Algoritmus:
--------
XX XX XX   Zeile voll
XX         Jetzt XXXXXX passt nicht, also nächste Zeile
XXXXXX
XXXXXX

Deine Lösung:

-------- Fehlermaß:
XX XX XX  1  
XX        6
XXXXXX    2 
XXXXXX    2


Besser wäre aber

-------- Fehlermaß:
XX  XX    2
XX  XX    2
XXXXXX    2
XXXXXX    2

Abgesehen davon: Der Lösungsvektor sollte nicht die Längen enthalten, sondern die Indizes - und sollte mit 0 anfangen, und mit n enden. (Das mit der 0 hatte ich auch übersehen). Irgendeinen Fehler hat deine Ausgabe auch noch, weil die ersten beiden Längen nicht ausgegeben werden.

BTW: Es könnte hilfreich sein, sich Methoden zu schreiben wie
private static float computeSum(int m, int l[], List<Integer> i) ....
(die die Summe berechnet, die am Ende der ersten Zeile der Definition der 'Ausgabe' steht)
und eine Methode
private static float computeMax(int l[], int L, List<Integer> i)
die das Maximum berechnet, das es zu minimieren gilt. Eine zusätzliche Methode
private static void print(int l[], int L, List<Integer> i)
die die Konfiguration bei der Lösung 'i' ausgibt (und ggf. auch gleich die Werte für jede Zeile) kann auch nicht schaden.

 

[Marco13]

So als Nachtrag: Dieses Problem ist ja schon sehr praxisrelevant. Das Textsatzprogramm "Latex" verwendet einen "ähnlichen" Algorithmus (wobei dort noch Silbentrennung berücksichtigt wird). Es ist dabei tatsächlich so, dass dieses Problem als ein "Kürzeste-Wege-Problem" aufgefaßt wird. Dabei ist die "Länge des Weges" eben die "Häßlichkeit" einer Zeile (und die "Häßlichkeit" besteht eben aus "großen Lücken").

 

[Gast]

Ok, also ich hab den Greedy Algorithmus erstmal berichtigt. Ich werd den Algo nochmal komplett neuschreiben, aber will halt erstmal den jetzigen zumindest einigermaßen richtig haben.

import java.util.ArrayList;

public class Blocksatz {

	public static void blocksatz(int maxline, int[] input){
		int currentValue=0;
		ArrayList<Integer> output= new ArrayList<Integer>();
		for(int i=0;i<input.length;i++){
			if(input[i]>maxline){
				System.err.println("Word "+ i+" of the input text is too big.");
				break;
			}
			// Hier gehts los
			else{
				if(input[i]+currentValue<=maxline){
					currentValue=input[i]+currentValue;
				}
				else{
					System.out.print(i-1+" ");
					output.add(i-1);
					currentValue=input[i];
					
				}
			}
			
			
		}
		System.out.print(input.length-1);
		output.add(input.length-1);
	}
	
	public static void main(String[] args){
		int zeilenLaenge = 15;
		int[] eingabeFolge=  {13,2,2,3,14,7,9,10,12,8,5} ;
		blocksatz(zeilenLaenge,eingabeFolge);
	}
}

Also, für mich bereitet jetzt noch diese 0 Probleme...
Warum soll der Vector von 0 bis n gehen?
Also n is klar, weil das n'te input Element natürlich ganz am Ende steht. Aber 0?
Das hieße ja, dass das Element mit index '0' in der ersten Zeile am Ende steht. Das hieße dass das erste Element die Zeile komplett ausfüllen müsste? ODer sehe ich das jetzt falsch. Ich versteh das mit der '0' ehrlich gesagt grad nicht so ganz.
Und spielt die 0 überhaupt eine Rolle? Ich meine der Ausgabevector soll ja von i1 bis in gehen und i1 =! i0.
Und jetzt muss ich mir das von dir angesprochene Problem erstmal durch den Kopf gehen lassen, also die Zwischenräume (und den Frust) zu minimieren ...
Aber schonmal danke an dieser Stelle. Ich weiß deine Hilfe wirklich zu schätzen.

 

[Marco13]

Jetzt fehlt noch die 0 als erstes Element von "output" (das braucht man, damit die nachfolgenden Berechnungen für die Summen und das Maximum "aufgabenstellungsnah" implementiert werden können), und dann... kannst du es neu schreiben :bae:

 

[Gast]

Sooooo,
Also ich hab mir das nochmal überlegt. Hab auch bissl was zu gelesen und bin nun zum entschluss gekommen, dass eine Umstellung der Strategie wohl sinnvoller wäre *hust*.
Also, vorgehen will ich wie folgend. Ich berechne die Minima Werte aller aneinander Hängenden Teilsummen.
Also bei ner Menge von 4 Elementen berechne ich folgende Teilsummen:
1,2,3,4,12,23,34,123,234,1234.
So die speicher ich mir mal alle ab.
Und für die einzelnen Teilsummen errechne ich mir halt immer das Minimum, so dass ich mir quasi den perfekten weg aufbauen kann...
An sich ist das ja so mehr oder minder was in der Angabe steht....
Nur.... Diese verfluchte Angabe, ich blicke einfach nicht so ganz durch was mir diese kryptischen Symbole sagen wollen :/...
Vorallem der Teil mit min(max (Summe-....)) wäre interessant.

Sorry, normalerweise bin ich nicht so begriffsstutzig, aber diese Aufgabe überfordert mich irgendwie.
Also wäre über erneute Hilfe, bezüglich der entzifferung des Mathematischen codes dankbar .