Knapsack Problem: Algorithmus?

Status
Nicht offen für weitere Antworten.
K

kiwisTarista

Gast
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
 

Hilefoks

Bekanntes Mitglied
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. ;-)
 
G

Guest

Gast
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

Top Contributor
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

Bekanntes Mitglied
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
 
G

Guest

Gast
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...?
 
K

KiwisTar

Gast
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 :p
Gruss
Freddy
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Z Analysemuster - Welches nehme ich für diese Problem? Softwareentwicklung 0
L Design Patterns zu abstraktem Problem Softwareentwicklung 2
C Regex Problem Softwareentwicklung 1
TheJavaKid RegEx Problem Softwareentwicklung 2
C Regex-Problem Softwareentwicklung 24
C GIT Einstieg - Problem Softwareentwicklung 12
H Problem mit jsp:setproperty Softwareentwicklung 10
B Regex-Problem mit replace außerhalb des matching bereichs liegender Zeichenketten Softwareentwicklung 2
Landei MS-Access-Problem Softwareentwicklung 3
TiME-SPLiNTER Banales regEx-Problem Softwareentwicklung 2
A 8 Damen Problem (Backtracking) Softwareentwicklung 2
U xmlvm-Problem: Der erzeugte Obj-C-Code erzeugt Fehler in Apple's Xcode SDK Softwareentwicklung 3
S Subversion und Source Folder Problem. Softwareentwicklung 6
G PHP Problem: Geltungsbereich von Variablen Softwareentwicklung 3
L Problem mit Vererbung Softwareentwicklung 6
C Ein Problem mit der RSA Versschlüsselung Softwareentwicklung 3
W Problem mit Umlauten in xml Dateien auf englischen Systemen Softwareentwicklung 7
H Problem Programmieren Softwareentwicklung 12
H Problem mit eclipse Softwareentwicklung 3
M IllegalStateException - Problem mit GUI und Observer pattern Softwareentwicklung 4
B JavaScript/JSON Problem Softwareentwicklung 2
m@nu Problem mit einer RegEx Softwareentwicklung 4
MTiN Problem mit Rot/Schwarz-Baum Softwareentwicklung 1
F Problem mit DOS-Box Softwareentwicklung 2
A Problem mit Datum-Formatierung Softwareentwicklung 2
M Traveling Salesman Problem Softwareentwicklung 6
S Problem PJIRC java-applet Softwareentwicklung 4
rambozola problem mit division in oracle Softwareentwicklung 2
Icewind Problem mit der OOP Softwareentwicklung 4
G Problem mit ActionListener Softwareentwicklung 7
C Mysql-Frage(Problem mit nicht durchgeführten Zugriff) Softwareentwicklung 5
R Algorithmus Softwareentwicklung 1
G Anzahl der Rekursionsaufrufe eines DFS Algorithmus Softwareentwicklung 16
S Algorithmus für perfekte Kombination Softwareentwicklung 2
J Gibt es eine Algorithmus dafür??? Softwareentwicklung 5
U tichy algorithmus Softwareentwicklung 2
D Algorithmus um Wiederholungen zu finden Softwareentwicklung 5
U Komplexität eines Algorithmus Softwareentwicklung 1
S Algorithmus zur Planung der Nachprüfungen Softwareentwicklung 10
G Gewichtung auswerten? [Algorithmus auswerten] Softwareentwicklung 3
Z Algorithmus (Routenberechnung) Softwareentwicklung 18
T Sudoku Algorithmus Softwareentwicklung 12
M [Algorithmus] Matrix nach Untermatrix durchsuchen Softwareentwicklung 15

Ähnliche Java Themen


Oben