Packproblem

B

Baunty

Mitglied
Hallo liebe Java Community,

ich muss für die Uni ein Programm schreiben, welches es ermöglicht ein beliebiges Rechteck so oft wie möglich in ein größeres Rechteck zu platzieren.

Ich habe leider überhaupt keine richtige Idee wie ich das ganze anpacken soll. Ich habe über einen rekursiven Algorithmus nachgedacht, der alle Möglichkeiten durchgeht und die besten Werte übernimmt, allerdings denke ich die ganze Zeit in einem Koordinaten bzw. Reihen-Spalten-Prinzip. Wenn allerdings beispielsweise 2 Rechtecke längst angeordnet sind, und dann 2 breit, dann ist die 2. Reihe ja sozusagen nicht vollständig.

Hat jemand vllt. schon einmal über soetwas nachgedacht und kann mir eine Gedächtnisstütze geben? Vorallem muss nachher das ganze noch bildlich dargestellt werden, ich muss also irgendwie genau wissen wo die Pakete liegen - das ganze also im Koordinatensystem zu machen ist sicherlich unlogisch.

Eine Idee wäre z.B. jedes folgende Paket immer an der nächst möglichen Stelle ganz links, oben im Rechteck anzuordnen. Und rekursiv dann alle Möglichkeiten durchzugehen und die Beste zu wählen - ich weiß allerdings nicht wie ich das umsetzen soll.

Ich suche nicht nach einer lösung - lediglich ein Denkanstoß wäre gut ;)

Liebe Grüße
 
R

remy

Aktives Mitglied
Vor einem Denkanstoß hab ich noch eine kleine Verständnisfrage:

Gegeben ist ein "großes" Rechteck sowie ein "kleines" Rechteck, letzteres soll vervielfacht werden und in dem großen Rechteck platziert werden, ohne dass sich die Kanten überschneiden?!
Darf das kleine Rechteck gedreht werden? Falls ja, müssen dann alle Rechtecke gedreht werden?
 
M

Marco13

Top Contributor
Können die Rechtecke auch gedreht sein? Soll immer nur das gleiche Rechteck einsortiert werden, oder unterschiedliche?

EDIT: Da war ich wohl zu lahm...
 
T

Tomate_Salat

Gast
Ich hätte jz die Idee(ohne drehung von den Rechtecken): ein Rechteeck mit den Maßen 4x3
Darein sollen x Rechtecke von der größe 2x2
Maximale R in X-Richtung: [c]mx=4/2=2[/c]
Maximale R in Y-Richtung: [c]my=3/2=1[/c] (natürlich gerundet)
Das ganze Multipliziert ergäbe: es passen 2 Rechtecke.

Also: [c]f(R1,R2)=(R1.x/R2.x)*(R1.y/R2.y)[/c]

in meinen Tests erziehle ich damit gute Ergebnisse.
 
F

Firephoenix

Gast
Hi,
interessant wäre auch, ob man das große Rechteck einfach nur kachelweise auffüllen soll, oder ob über drehungen ein optimales Ergebnis herausgeholt werden soll.
Die erste Version wäre nämlich simples durchrechnen, die 2. wohl eher ein Fall für eine Baumoptimierung die alle Möglichkeiten durchspielt.
Gruß
 
D

Dow Jones

Gast
Baunty hat gesagt.:
ich muss für die Uni ein Programm schreiben, welches es ermöglicht ein beliebiges Rechteck so oft wie möglich in ein größeres Rechteck zu platzieren.
Zum Vergrößern anklicken....

Nice... Das "Manufacturer's Pallet Loading Problem" gilt soweit ich mich erinnere als NP-vollständig. Da wirst du wohl nicht drum herum kommen mal zu googeln und ein paar Papers zu lesen. :rtfm:
Sag bitte Bescheid wenn du's fertig hast; bin auch neugierig!


PS: Oder du rufst von deinem Programm aus klammheimlich einen online solver auf. :D
 
D

Dow Jones

Gast
Tomate_Salat hat gesagt.:
Das teil widerlegt mit dem ersten Beispiel meinen Vorschlag. ... na ganz toll :D
Zum Vergrößern anklicken....

Und dabei machen die es noch nicht einmal richtig... :joke:

packing.png
 
B

Baunty

Mitglied
Hallo Leute,
danke für eure Antworten.
Da Kartons auf eine Palette gestapelt werden sollen werden dürfen die Kartons nur um 90°C gedreht werden, sprich die Kartonkanten sind immer parallel zur Palettenkante. Das Online-Ding ist sozusagen genau das, was ich auch machen soll.

Ich habe echt überhaupt keine Idee wie so ein Algorithmus aussehen soll.
Vielleicht hätten wir uns ne andere Aufgaben aussuchen sollen :D...
 

Aktuelle Jobs

Neue Themen


Oben