[EDIT] Tiefensuche / Depth-First-Search / Greedy Algorithmus

[Stalafin]

Zuerst: Ich bin noch ein ziemlicher Neuling, was Java angeht. (gut, auch was Programmieren angeht...)

Folgendes Problem:
Ich habe einen bestimmten Betrag an maximaler Arbeitszeit (in Minuten) "workDay", den ich pro Tag aufbringen muss.
Nun gilt es, diese Arbeitszeit aufzufüllen mit verschiedenen Tätigkeiten, wobei diese verschiedenen Tätigkeiten individuell unterschiedliche Zeiten "act_time" haben.
Diese Zeiten werden alle in einem Array gespeichert (soweit habe ich das ja alles auch noch geschafft).

Nun möchte ich ausrechnen, welche dieser Tätigkeiten ich wie kombinieren muss, um die höchstmögliche Arbeitszeit zu erreichen, ohne dabei mein Pensum pro Tag zu überschreiten (so viel wie nötig, sowenig wie möglich). Dabei gilt - die Arbeitszeit pro Tag ist der Wert, der nicht überschritten werden darf.
Außerdem darf eine Tätigkeit nur einmal durchgeführt werden.
Die Tätigkeiten und die Arbeitszeit sollen veränderbar sein (d.h. das Programm weiß zuerst nicht, wie hoch das Arbeitspensum ist und wieviele Tätigkeiten wie lang dauern).

Ich habe nun den Begriff "Tiefensuche" oder "Depth-First-Search" gefunden. Ich denke, ich muss das Prinzip irgendwie in mein Programm implementieren, weiß aber nicht wie. Alle Beispiele im Internet gehen von Labyrinthen oder sowas aus (mein Problem ist ja ein anderes).


Kann mir dabei vielleicht jemand helfen (und vielleicht einen Beispiel-Code geben)?


EDIT: Ich habe noch einen sogenannten "Greedy-Algorithmus" gefunden. Eignet der sich vielleicht besser, das Problem zu lösen?

 

[LoN_Nemesis]

Dein Problem ist ein vereinfachtes "Backpack Problem" oder auch "Rucksack Problem" auf deutsch. Dafür gibt es Standard Lösungen, such mal nach diesen Begriffen in google.

Bei dem Backpack Problem geht es darum, dass man einen Rucksack hat, in den nur ein bestimmtes Gewicht reinpasst. In deinem Fall ist das maximal Gewicht die Arbeitszeit pro Tag. Nun hat man viele verschiedene Gegenstände, die alle eine Wert und Gewichtsangabe besitzen. Man möchte nun den Rucksack so packen, dass der Wert maximiert (oder minimiert) wird.


Beispiel: http://www.edm2.com/0601/backpack.html aber vielleicht gibts noch bessere Seiten.

 

[Stalafin]

Also ist der erste Schritt, einen Algorithmus zu finden, der sämtliche Möglichkeiten findet, die Gegenstände zu kombinieren (wie in deinem Link).

Nehmen wir an, ich habe folgende Gegestände: 0, 1, 2 und 3.

Die Möglichen Kombinationen für diese sind:

"0"
01
012
0123
013
02
023
03
1
12
123
13
2
23
3

Hm, das sind 15 Möglichkeiten. Habe ich einen Denkfehler oder müssten das nicht 2^4=16 sein?

Naja, egal.


Ich werde aus dem Codebeispiel aus dem link nicht ganz schlau.

Kann mir vielleicht jemand helfen, den zu übersetzen? Wie würde der Code aussehen, um alle Kombinationen rauszubekommen?

 

[dieta]

Der Code den du für deine Liste da verwendet hast, ist jedenfalls falsch.
Z.B. die "0" fehlt ganz und die "012" ist doppelt.

[edit]Ausserdem sind das nur 14 Kombinationen :wink: [/edit]

 

[Stalafin]

Dass die 0 nicht angezeigt wurde war nicht mein Fehler - die gemeine Forensoftware zeigt die 0 am Anfang nicht ein.
Das zweite 012 war ein Vertipper - sollte 0123 heißen.

Ist jetzt korrigiert.

Nun - hast Du vielleicht einen Tipp für mich?

 

[dieta]

Ich hab' jetzt mal eine Methode geproggt, die dir alle Möglichen Kombinationen der Elemente eines Arrays ausgibt:

	private void ts()
	{
		String[] elements = new String[4];
		
		elements[0] = "0";
		elements[1] = "1";
		elements[2] = "2";
		elements[3] = "3";
		
		suche("", elements);
		
	}
	
	private void suche(String found, String[] elements)
	{
		for(int i=0; i<elements.length; i++)
		{
			String newFound = found + elements[i];
			System.out.println(newFound);
			String[] newElements = new String[elements.length -1];
			for(int j=0; j<newElements.length; j++)
			{
				if(j < i)
				{
					newElements[j] = elements[j];
				}
				else
				{
					newElements[j] = elements[j+1];
				}
			}
			suche(newFound, newElements);
		}
	}

[edit]Das "founded" ist jetzt angepasst, ist halt 22 uhr abends...[edit]

 

[Stalafin]

Danke Mann!
Vielen Dank für Deine Hilfe.
Werde mir das mal genauer anschauen und versuchen, zu verstehen.


(Nur eines... "founded" wird "found" geschrieben )


EDIT: Der Aufruf "Suche ("", Elements)" Gibt den gesamten String weiter? Ich war mir bisher immer nicht sicher, wie ich Strings weitergeben soll.
Wie funktioniert das ganze mit Ints oder Doubles?