5.8

[Ramses]

Mein Vorschlag für den Algorithmus wäre:

B[1..5] Array Bonuspunkte
Z[1..5] Array Zeit
W[1..5] Array Wert
L[1..5] Array Lösung
für i=1 bis 5
{W[i] = B[i]^2/Z[i]} //Ich quadriere die Bonuspunkte um sie wertvoller gegenüber der Zeit zu machen

k=1; Zeit=0;
sollange Zeit <= 180 && E x Element W <> 0 // und es existiert ein Element x in W das ungleich 0 ist

{i= max W // Index des grössten Wertes in W
falls Zeit + Z[i] > 180
{E[i] =0
goto weiter}
sonst
{Zeit = Zeit + Z[i];
L[k] = B[i];
E[i]=0;}
weiter: k++;}
Punkte =0; x=1;
solange L[x] <> 0
{Punkte =Punkte +L[x]}
return Punkte;

Der Algorithmus scheint zumindest für dieses Beispiel zu funktionieren.

[fuxi17]

Ich habe ganz einfach den ALgorithmus 52 vom Skript genommen.
Wert => Bonuspunkte
Gewicht => Zeit
Grösse des Rucksackes => Gesamtzeit die verfügbar ist

[Pellegatti]

@fuxi17:
gar keine blöde idee ;) werd ich auch so machen :D

[nonamenobody]

So auf die Art: "Von dem Algorithmus wissen wir nicht, was für eine Laufzeit er hat, also könnte sie ja auch subexponentiell sein." (Ich hab es zumindest dem Skriptum nicht entnehmen können.) http://hades.gothic.at/iforum/images/smilies/biggrin.gif

Bin gespannt, was der Tutor zu so was sagen würde...

lg
Philipp

[templar]

So auf die Art: "Von dem Algorithmus wissen wir nicht, was für eine Laufzeit er hat, also könnte sie ja auch subexponentiell sein." (Ich hab es zumindest dem Skriptum nicht entnehmen können.) http://hades.gothic.at/iforum/images/smilies/biggrin.gif

Bin gespannt, was der Tutor zu so was sagen würde...

lg
Philipp

Naja, da das Problem offensichtlich äquivalent zum 0/1-Rucksackproblem ist, gibt's keine polynomielle Lösung, denk ich mal. Außer du kannst zeigen, dass P=NP gilt, aber dann wärst du ein reicher Mann ;).
Dynamische Programmierung zeigt bei den Werten aber pseudopolynomielle Laufzeit, weil c_opt (maximaler Lösungswert) relativ gering ist und für die Laufzeit O(N*C_opt) gilt.
Also ich denk besser als so wirds kaum gehen.

[Merlin]

Ich habe ganz einfach den ALgorithmus 52 vom Skript genommen.
Wert => Bonuspunkte
Gewicht => Zeit
Grösse des Rucksackes => Gesamtzeit die verfügbar ist Was heisst hier Seite 52 ?
Die Implementierung einer ADT ???
Meinst du nicht etwas Seite 138???

[kaeptn]

Was heisst hier Seite 52 ?
Die Implementierung einer ADT ???
Meinst du nicht etwas Seite 138???

Er schrieb _Algorithmus_ 52.
Nicht _Seite_ 52.
Ja, Alg. 52 ist auf Seite 138!
*g*

Bye,
Fritz

[ChristofNeutron]

und wie arbeitet dieser Algo (52) jetzt wirklich? Irgendwie hab ich da keinen genauen Plan???
Kann mir da vielleicht jemand einen Anfangstipp geben?

[Havoc]

und wie arbeitet dieser Algo (52) jetzt wirklich? Irgendwie hab ich da keinen genauen Plan???
Kann mir da vielleicht jemand einen Anfangstipp geben?

weiss net ob im neuen skriptum der algorithmus auch der dynamische programmierung 0/1knapsack is aber falls ja denk ich mal dass das net so schwer sein sollt:

fuktioniert eigentlich wie die normale enumeration,
die tupel die die rucksackeigenschaft verletzten werden nicht in den baum aufgenommen.
wenn der baum dann fertig for die steht bestimmst du bottom-up also von unten nach oben welche tupel in deine lsg aufgenommen werden das heisst du suchst dir in jeder ebene die tupel mit der gleichen bonuspunkteanzahl und das mit der geringsten zeit wird mitgenommen die anderen scheiden aus!!

die optimale lsg is dann das tupel mit der größten anzahl an bonuspunkten und kleinster zeit!!

in unseren fall schätz ich falls mir kein fehler unterlaufen is
({B,C,D,E};{30},{180})
:ausheck:

[NightHaG]

hat sich erübrigt