abumaster
25-05-2003, 15:41
mein Vorschlag,(hab noch nicht überprüft obs wirklich funzt):
Ich bilde mir zum besseren Verständnis einen Entscheidungsbaum mit den Pfaden EINPACKEN/NICHTEINPACKEN
folgedes gilt: wenn ich das Element hinzufüge und die Obere Schranke meines Unterbaumes kleiner ist als die Untere Schranke des gesamten Baumes kann ich diesen Unterbaum spritzen.
somit muss ich wesentlich weniger Pfade durchlaufen. Wenn ich an einem Blatt angekommen bin Speichere ich den Wert und vergleich ihn mit den anderen Blättern.
der Baum sieht folgendermassen aus
0
/ \
a !a
/ \ / \
ab a!b !ab !a!b
Um die globale obere,untere Schranken zu berechnen muss ich die Elemente nach ihrem Nutzen absteigend sortieren.
Nun packe ich so viele Elemente fraktional ein bis er voll ist (d.h. es darf auch noch ein Teil des letzten El. genommen werden). somit erhalte ich die obere Schranke O.
das selbe Verfahren nur nicht fraktional. (d.h. das Element das ich aufteilen müsste kommt nich mehr rein).
somit erhalte ich die obere schranke U.
Somit habe ich auf alle Fälle eine Lösung mit Wert U.
Alle Lösungen die darunter sind kann ich vergessen.
Nun konstruiere ich den Baum und suche noch die Optimallösung.
start{
sortiere Elemente nach dem Nutzen (c/w)
berechne O, U Schranke //wie oben beschrieben
init: x[1...n]=[0...0];
einpacken(x, aktpos=1); //befinde mich in der Wurzel, muss entscheiden ob 1.El dazukommt oder nich
vergleiche die Ergebnisse und nimm das Beste
}
//Entscheidet anhand der neu entstehenden Schranken ob ein Element eingepackt wird oder nicht(auch beides möglich)
//und springt dann rekursiv tiefer in den Baum hinein
einpacken (x, aktpos) {
gewählt=false;
Wenn(OSchr(x,aktpos) >= U){
einpacken(x,aktpos+1)
gewählt=true;
}
x[aktpos]=1; //setze das aktElement auf "eingepackt" und betrachte die Schranke
Wenn(OSchr(x,aktpos)>=U){
einpacken(x,aktpos+1)}
gewählt=true;
Wenn gewählt = false; //bin offensichtlich am Blatt angekommen
}
//berechnet die obere Schranke eines Teilbaumes
OSchr(x,aktpos){
Gewicht = Summe von 1 bis aktpos (w[i]*x[i]); //die Elemente von 1 bis aktpos stehen schon fest
aktoos++;
while(Gewicht + w[aktpos] <= K){ //solange ich noch was einpacken kann
Gewicht += w[aktpos];
}
Wenn Gewicht < K{
splitte Element[aktpos] sodass der Rucksack voll ist; //Wieder fraktional zur Berechnung der lokalen Oberen Schranke
}
}
Ich bilde mir zum besseren Verständnis einen Entscheidungsbaum mit den Pfaden EINPACKEN/NICHTEINPACKEN
folgedes gilt: wenn ich das Element hinzufüge und die Obere Schranke meines Unterbaumes kleiner ist als die Untere Schranke des gesamten Baumes kann ich diesen Unterbaum spritzen.
somit muss ich wesentlich weniger Pfade durchlaufen. Wenn ich an einem Blatt angekommen bin Speichere ich den Wert und vergleich ihn mit den anderen Blättern.
der Baum sieht folgendermassen aus
0
/ \
a !a
/ \ / \
ab a!b !ab !a!b
Um die globale obere,untere Schranken zu berechnen muss ich die Elemente nach ihrem Nutzen absteigend sortieren.
Nun packe ich so viele Elemente fraktional ein bis er voll ist (d.h. es darf auch noch ein Teil des letzten El. genommen werden). somit erhalte ich die obere Schranke O.
das selbe Verfahren nur nicht fraktional. (d.h. das Element das ich aufteilen müsste kommt nich mehr rein).
somit erhalte ich die obere schranke U.
Somit habe ich auf alle Fälle eine Lösung mit Wert U.
Alle Lösungen die darunter sind kann ich vergessen.
Nun konstruiere ich den Baum und suche noch die Optimallösung.
start{
sortiere Elemente nach dem Nutzen (c/w)
berechne O, U Schranke //wie oben beschrieben
init: x[1...n]=[0...0];
einpacken(x, aktpos=1); //befinde mich in der Wurzel, muss entscheiden ob 1.El dazukommt oder nich
vergleiche die Ergebnisse und nimm das Beste
}
//Entscheidet anhand der neu entstehenden Schranken ob ein Element eingepackt wird oder nicht(auch beides möglich)
//und springt dann rekursiv tiefer in den Baum hinein
einpacken (x, aktpos) {
gewählt=false;
Wenn(OSchr(x,aktpos) >= U){
einpacken(x,aktpos+1)
gewählt=true;
}
x[aktpos]=1; //setze das aktElement auf "eingepackt" und betrachte die Schranke
Wenn(OSchr(x,aktpos)>=U){
einpacken(x,aktpos+1)}
gewählt=true;
Wenn gewählt = false; //bin offensichtlich am Blatt angekommen
}
//berechnet die obere Schranke eines Teilbaumes
OSchr(x,aktpos){
Gewicht = Summe von 1 bis aktpos (w[i]*x[i]); //die Elemente von 1 bis aktpos stehen schon fest
aktoos++;
while(Gewicht + w[aktpos] <= K){ //solange ich noch was einpacken kann
Gewicht += w[aktpos];
}
Wenn Gewicht < K{
splitte Element[aktpos] sodass der Rucksack voll ist; //Wieder fraktional zur Berechnung der lokalen Oberen Schranke
}
}