Theoretisches Problem

Hallo zusammen,

ich habe eine kleine Herausforderung an all diejenigen, die sich gerne die Zähne an Kniffelaufgaben ausbeissen
Ich habe ein rechteckiges Tablett der Größe Xt und Yt. Auf dieses Tablett sollen rechteckige Kisten unterschiedlicher Größen gestellt werden (Maße Kisten Xk und Yk). Gesucht ist ein Algorithmus, der einen passenden freien Platz für eine Kiste auf dem Tablett sucht und diese dort ablegt. Kleine Verschärfung: Wenn eine Kiste mal ihren Platz hat, kann sie nicht mehr verschoben oder deplatziert werden.
Ist ein aktuelles Problem, das ich gerade habe und alle, die ich gefragt habe, haben sich die Zähne daran ausgebissen.
Bin gespannt ob´s von Euch jemand hinbekommt?!

Grüße, Tobias

Nein zum Glück nicht, ich schreibe an einer Datenbanksoftware (Werkstudent), die bei mir in der Firma das Shuttle-Regal verwaltet. Ich suche dabei nach einer Methode, die mir auf den Regalböden automatisch einen passenden freien Platz sucht und das so, dass immer die kleinste mögliche Lücke verwendet wird (um Platz zu sparen). Leider weiß ich an dieser Stelle nicht weiter.

Viele Grüße,

Tobias

Super danke, hat mich zumindest auf die richtige Spur gebracht. Habe mir mal das zweidimensionale Bin-Packing (online-Verfahren) angesehen und das müsste in etwa der Problematik entsprechen. Ich habe in einigen Quellen gelesen, dass es eine Flut von Algorithmen die das Problem lösen sollen geben soll, habe nur nichts derart gefunden. Interessant wären natürlich Lösungen für die first-fit und die best-fit Methode. Weis evtl. jemand einen Link auf Programmquellen oder ein gutes Buch (praxisorientiert), das nicht zu tief in die Theorie und Komplexität der Algorithmen eingeht sondern eher auf die Programmierung ausgelegt ist?

PS: laborg, Du hast mir sehr weitergeholfen, danke !!!