Effizientes Pakete packen

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

AMY

Betreff: Effizientes Pakete packen

BeitragDi, Mai 14, 2019 4:52
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich brauch mal ein paar Denkanstöße. Es geht darum ein Paket am effizientesten zu packen. Das Problem dabei sind sicher die vielen Möglichkeiten die man hat.
Grundlage:
- es gibt 8 verschiedene Verpackungen in die gepackt werden kann
- Es gibt mehr als 10 paketgrössen die gepackt werden müssen (diese Liste sollte erweiterbar sein)
- Jedes Paket kann natürlich in 6 verschiedenen richtungslagen gepackt werden (Also die Pakete dürfen gedreht werden)
- Optional würde ich auch gerne das Gewicht Mit einbeziehen. Da ein maximal Gewicht pro gesamt verpackung nicht überschritten werden darf.

Ich hoffe ihr könnt mir ein wenig Licht im dunkel geben ^^
Projekte: www.amyscbi.de
I never comment my sourcecode. What's HARD to write must be HARD to read!

SpionAtom

BeitragDi, Mai 14, 2019 9:20
Antworten mit Zitat
Benutzer-Profile anzeigen
Klingt erstmal grundlegend nach einem Kombinatorikproblem.

Sicher kann man Vorüberlegungen anstellen.
- Passt das Gesamtvolumen der Pakete überhaupt in die Verpackung?
- Passen die Pakete von ihren Abmessungen in die Verpackung?
- Sollen gleiche Dinge bevorzugt zusammenverpackt werden?
- Muss irgendwas oben liegen?

Hast du noch mehr Infos zu deinem Problem?
Was ist die Eingabe? Einfach eine Liste von Paketen mit Größenangaben und Gewichten?

Und was soll rauskommen? Eine möglichst kleine umschließende Verpackung von den 8? Genug Platz für Luftpolster?

Faul und dumm wie ich bin, würde ich es am Ende einfach bruteforcen.... Rolling Eyes Laughing


Edit: Wir hatten mal einen Wettbewerb, bei dem es darum ging Grafiken möglichst platzsparend in einem Bild anzuordnen, ist zwar nur 2D, aber vielleicht gibt das noch Ideen.
https://www.blitzforum.de/foru...hp?t=39385

Dropbox Downloadlink
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080
  • Zuletzt bearbeitet von SpionAtom am Do, Mai 16, 2019 13:22, insgesamt einmal bearbeitet

AMY

BeitragDi, Mai 14, 2019 14:30
Antworten mit Zitat
Benutzer-Profile anzeigen
Das sind schonmal gute Überlegungen die ich noch gar nicht bedacht habe. Mit den Vorbereitungen ist auch ne gute Idee.
Mit der Idee das was oben liegen muss klingt auch gut würde ich aber vielleicht sogar noch ausweiten mit einer sagen wir mal Festigkeit weiss nicht wie ich es sonst beschreiben soll.


Es kommen immer Paletten mit Paketen an. Diese müssen verpackt werden. Auf jedem Paket ist ein Code, dieser kann gescannt werden. Mit diesem kann man Grösse und Gewicht ermitteln also dies ist im System hinterlegt.
Dies zu bruteforcen war auch meine Idee. Die Geschwindigkeit spielt dabei auch keine starke Rolle solange es keine 10min braucht ^^.
Genau am Ende sollte die kleinstmögliche Verpackung gefunden werden.
Wie würdest du die Listen intern abspeichern? Am besten mit Types oder geht auch dim? Bin bei types noch immer nicht so bewandert hab mich aber zumindest schon mal damit auseinander gesetzt. Eine Hilfestellung dazu wäre dann ganz gut. Müssten es nicht dann zwei types sein?

Edit 15:12
Hab dein Edit zu spät gesehen. Erst als meine Antwort fertig war. Hab mir mal den BCC angesehen. Leider ist nur noch der Beitrag von Xeres anschaubar. Dieser ist in blitzmax geschrieben und da ich Grad unterwegs bin nicht vernünftig lesbar. Ich guck mir den heute Abend nochmal am Rechner an. Mal seh'n ob ich bmax Code verstehe, da ich sonst nur mit blitzplus und blitz3d unterwegs bin. Ich hab auf dem ergebnisbild sogar schon nen Fehler gefunden Wink
Projekte: www.amyscbi.de
I never comment my sourcecode. What's HARD to write must be HARD to read!

SpionAtom

Betreff: Raster

BeitragDo, Mai 16, 2019 10:33
Antworten mit Zitat
Benutzer-Profile anzeigen
Man kann sich das Problem etwas vereinfachen, indem man alle Boxen an ein Raster anpasst, und nur diese Rasterkoordinaten verwendet. Also Ganze Zahlen wenn man so will, und keine Kommazahlen.

Dann gibt es vielleicht eine nicht ganz getreue Abbildung der Realität (Aus Box mit den Ausmaßen 3.7 x 4.8 x 5.6 wird dann Box 4 x 5 x 6, und aus Position (1.2 | 2.8 | 3.9) wird dann Position (2 | 3 | 4)), aber durch den Abstraktionsgrad gewinnt man eine Vereinfachung des Algorithmus und auch eine Zeitersparnis beim errechnen.

(Vielleicht versuche ich mich mal an einem 2D Beispiel)
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

AMY

BeitragDo, Mai 16, 2019 10:50
Antworten mit Zitat
Benutzer-Profile anzeigen
Leider hab ich es noch nicht geschafft mir das BCC Packprogramm auf dem Rechner anzusehen. Einfach zu wenig Zeit ^^. Mach ich aber noch die Tage.
Ich würde es schon lieber genauer haben. Die Zeit Spielt wie ich schon schrieb nicht die Rolle dabei.
Projekte: www.amyscbi.de
I never comment my sourcecode. What's HARD to write must be HARD to read!

DAK

BeitragDo, Mai 16, 2019 13:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Im Endeffekt ist das eine Variante vom Rucksackproblem. Das Problem fällt unter die Kategorie NP-Vollständig. Das heißt, für eine perfekte Lösung musst du jede mögliche Kombination durchprobieren, was recht rasch recht unmöglich wird. Bruteforcen allein wird dabei (je nach Anzahl der Pakete) recht schnell unbrauchbar.

Um sowas zu lösen brauchst du ein gewisses Vorwissen in der Algorithmik und Blitz ist dafür nicht unbedingt die sinnvollste Sprache, da es dir noch nicht mal sinnvolle Datenstrukturen liefert und schon gar nicht irgendwelche hilfreichen Bibliotheken existieren.

Wahrscheinlich fährst du besser wenn du dir zumindest mal Python anschaust...
Gewinner der 6. und der 68. BlitzCodeCompo

SpionAtom

Betreff: Container Loading Problem

BeitragDo, Mai 16, 2019 14:32
Antworten mit Zitat
Benutzer-Profile anzeigen
Ja, richtige Informatiker dürfen sich gerne damit herumschlagen.

Bekannt ist das ganze unter der Bezeichnung "Container Loading Problem".

https://www.fernuni-hagen.de/w.../db426.pdf
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

AMY

BeitragDo, Mai 16, 2019 14:38
Antworten mit Zitat
Benutzer-Profile anzeigen
Naja auch wenn Blitz nicht die geeignetste Sprache ist versuche ich es mal damit wenn ich Zeit habe. Der Aufwand sollte sich auch nicht so gross werden das zumeist die Pakete so groß sind das maximal 40stk auf eine Palette passen. Aber ich danke euch dennoch für die nützlichen Tipps, Ich guck mir das mal alles in Ruhe an. Wenn ich Zeit habe nehme ich mich mal dem Problem an und melde mich bei Bedarf oder Fertigstellung hier wieder.
Projekte: www.amyscbi.de
I never comment my sourcecode. What's HARD to write must be HARD to read!

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group