Knapsack Problem: Algorithmus?

[kiwisTarista]

Tag zusammen,

sitze momentan an einem sogenannten knapsack problem und suche nach einem
geeigneten algorithmus zur loesung.
Das Problem in kurzform:

Habe einen container und boxen von drei verschienden typen, mit jeweils unterschiedlichem volumen / format und unterschiedlichem wert.

Nun brauch ich den maximal moeglichen wert der Beladung. Das Ergebnis muss nicht perfekt sein, aber einer guten durchschnitllichen wert ermitteln.

Bin um jeden tip dankbar
Gruss
kiwisTarista

 

[Wildcard]

Bitte sehr:
http://de.wikipedia.org/wiki/Rucksackproblem

 

[Hilefoks]

Ah - das alte Rucksackproblem aus Vorlesungen wie "Algorithmen und Datenstrukturen"?

Der Algorithmus den du suchst ist ein sogenannter Backtrack-Algorithmus. Informationen zu diesem im Allgemeinen und zum Rucksackproblem im besonderen findest du u.A. in der Wikipedia (und den dort angegebenen Links). Ansonsten sollte dir dann auch die Suchmaschine deiner Wahl, mit den richtigen Suchbegriffen gefüttert (zu finden in der Wikipedia), brauchbare Informationen bieten.

MfG,
Hilefoks

EDIT: Wildcard war schneller. ;-)

 

[Guest]

ehm jep danke schonmal, aber so wie ich das sehe koennen mir die info erstmal nicht weiter helfen...
Habe nat auch schon google angeschmissen, aber finde keinen algorithmus der sich mit der gleichen problemstellung befasst, da es ja auch gleichzeitig um das format der kisten geht...
Aber vielleicht hab ich auch nur was missverstanden/uebersehen... ?

 

[Wildcard]

Die Problemstellung bleibt doch die gleiche, oder?
Einen Copy/Paste Algorithmus wirst du nicht finden, du musst die bestehenden Lösungen für dich adaptieren.

 

[Hilefoks]

Wie Wildcard schon sagte - die Problemstellung ist immer die gleiche - deshalb kann man das ganze auch einen einheitlichen Namen geben, - eben das Rucksackproblem.

Quicksort, nur um mal einen anderen Algorithmus zu nennen, ist ja prinzipiell auch immer gleich - egal welche Daten er genau sortieren muss. Maximal muss der Quicksort-Algorithmus für ein gegebenes Problem nur an der Stelle angepasst werden wo der Vergleich (<,> oder =) stattfindet - der Algorithmus als solches arbeitet aber immer nach dem gleichen Prinzip. Hat man einmal Quicksort verstanden, kann man Quicksort für jedes Sortierproblem einsetzen (solange nicht andere Faktoren gegen Quicksort sprechen).

Versuch mal ein beliebiges Rucksackproblem und dessen Algorithmus zu verstehen - anschließend wird es dir leicht fallen diese Lösung auf dein Problem zu adaptieren.

MfG,
Hilefoks

 

[Guest]

das ich den anpassen muss ich mir natuerlich schon klar, nur ist mir nicht klar wie ich mit der erhoehten komplexitaet umgehen soll...

Wenn man nur die oft gewaehlten attribute gewicht, wert und volumen nimmt ist es ja noch relativ einfach, aber wie
handle ich anordnung der kisten im raum?

Stehe ich nur auf dem schlauch und das ist genau das gleiche...?

 

[KiwisTar]

ok habe jetzt gesehen dass mein problem 3 dimensional ist, falls jemand also einen algorithmus mit guter fitness fuer mein problem kennt, bitteschoen

Ansonsten danke fuer die beteiligung, werde wohl selber crawlen
Gruss
Freddy