Algorhytmus um geringsten Holzverbrauch zu ermitteln

[koin]

Hallo liebe Community,
stehe vor einem kleinen Problem Durch ein Bauprojekt benötige ich diverse längen Holz und möchte es natürlich genau passend haben, um so wenig wie möglich zu kaufen und zu tragen

Im Baumarkt kann ich 4 Verschiedene Längen kaufen.
1 x 2000mm
1 x 2500mm
1 x 3000mm
1 x 4000mm

und benötige 5 verschiedene Längen:
2 x 1470mm
2 x 2090mm
2 x 1354mm
1 x 1974mm
mindestens 6 x 638mm

nun meine Mathematik reicht nicht aus und Probieren hab ich schon, allerdings hätte ich gerne ein "Beweis" das es sich echt um die günstigste Kombination handelt.
Habe mir überlegt die Werte alle in Python einzutragen und über Schleifen jede mögliche Kombination zu prüfen und das Ergebnis, also den Geringsten Rest und die Geringste Balkenanzahl auszugeben, am liebsten auch mit der Aufteilung. Klingt auf Anhieb echt easy, allerdings hab ich als Programmieranfänger echt Schwierigkeiten überhaupt einen Sinnvollen Ansatz zu finden.

Hat jemand eine grobe Ahnung wie man die Worte, Codetechnisch umsetzen kann?

Mit freundlichem Gruß
koin

[EyDu]

Hallo und willkommen im Forum!

Und herzlich willkommen zum Bin-Packing-Problem, darauf bist du nämlich gestoßen. Wenn du wirklich das Optimum erreichen willst, dann musst du zwangsweise alle Kombinationen durchgehen, einen (viel) besseren Ansatz gibt es dafür nicht. Am besten überlegst du dir dazu, wie du das ganze Problem per Hand lösen würdest. Du könntest zum Beispiel einfach mal Zettel mit den entsprechenden Längen ausschneiden und dich ganz logisch durchprobieren.

Zwei ganz wichtige Überlegungen solltest du auf jeden Fall machen: Wie viele Stücke Holz brauchst du mindestens (um überhaupt auf die Länge zu kommen) und wie viele Stücke brauchst du höchstens, wenn du für jedes benötigte Stück Holz ein Stück Holz kaufst. Gut, die letzte Frage habe ich damit ja schon beantwortet

Jetzt hast du einen Minimalbedarf an Holz und einen Maximalbedarf. Das Optimum muss sich also irgendwo dazwischen befinden. Du musst jetzt nur noch alle Kombinationen von Holzstücken erzeugen, die in der Länge der Summe dazwischen liegen.

Es heißt übrigens Algorithmus, das hat nichts mit Musik zu tun

[sparrow]

Die nächste Frage wäre: wie oft darf denn ein eingesetztes Stück Holz gestückelt sein? Alle Reste zusammen einfach auf Länge nageln - das trägt doch nichts

[koin]

Hey danke euch

dem Kind einen Namen zu geben macht die Nachforschung schonmal was einfacher, denke werde mich nach der Arbeit heute mal dransetzen Den Holzbedarf einzuschränken auf Minimum und Maximum, darauf bin ich garnicht gekommen. Denke es wird dennoch schwerer umzusetzen als es sich anhört (zumindestens für mich).

@sparrow stimmt Die benötigten Längen sollten schon in einem Stück rauskommen^^ Die 5mm die ich beim Schneiden verliere lasse ich mal außer acht bei meiner Planung, so genau geht das eh nicht auf

[Hyperion]

Es gibt bestimmt "fertige" Solver für diese Problemklasse, die vermutlich heuristisch vorgehen dürften. Evtl. suchst Du einfach mal danach?

[Leonidas]

Es gibt bestimmt "fertige" Solver für diese Problemklasse, die vermutlich heuristisch vorgehen dürften.

Sogar in Python

[snafu]

Hier mal ein erster Versuch von mir:
https://gist.github.com/anonymous/03aa92a58e17bcb41f64

[EyDu]

@snafu: Das ist aber nicht die optimale Lösung. Wenn du mit Sortieren das P/NP-Problem lösen könntest, dann wäre da schon jemand drauf gekommen. Versuch mal diese Einstellung:

Code: Alles auswählen

needed_lumber = {5: 1, 4: 2, 3:1, 2:2}
dimensions = [10]

also der Menge, 5, 4, 4, 3, 2, 2.

Offensichtlich kommt man mit 2 Bins aus:
5, 3, 2
4, 4, 2

Durch deine Sortierung brauchst du drei:
5, 4
4, 4,
3, 2, 2

"dimensions" würde ich auch eher "sizes" nennen, das passt besser.

[snafu]

@EyDu: Ich habe nicht behauptet, dass dies die optimale Lösung sei. Wenn du weißt, wie man es für eine optimale Lösung implementieren kann, dann nur zu...

Mein Algorithmus nimmt sich das jeweils größte Stück und sucht sich dann den kleinsten Behälter aus, wo es reinpasst. Natürlich unter Berücksichtigung der Stücke, die schon im Behälter drin sind. Ich hatte versucht, diese Beschreibung zu implementieren. Dabei handelt es sich um ein Näherungsverfahren.

Bezüglich "dimensions" siehe:
http://en.wikipedia.org/wiki/Lumber#Dimensional_lumber

Hatte das mal frei interpretiert.

Hier eine verbesserte Version, die einen Logikfehler bei der Darstellung beseitigt und die Darstellung etwas verschönert:
https://gist.github.com/anonymous/4ac489a13ddff3ad2b04

Wie gesagt: Bessere Vorschläge sind willkommen. Idealerweise mit Code.

[EyDu]

@EyDu: Ich habe nicht behauptet, dass dies die optimale Lösung sei. Wenn du weißt, wie man es für eine optimale Lösung implementieren kann, dann nur zu...

In dem Thread ging es ja gerade darum, dass die optimale Lösung gefunden wird.

Wie gesagt: Bessere Vorschläge sind willkommen. Idealerweise mit Code.

Wie ich schon schrieb: Einfach alle Varianten durchprobieren, das lässt sich sehr leicht implementieren:

Code: Alles auswählen

Bestimme eine Untergrenze n für die mindestens benötigten Bretter
Bestimme eine Obergrenze m für die maximal benötigten Bretter

Erzeuge alle möglichen Brettkombinationen C mit Anzahl n bis m aller verfügbaren Bretter:
    Test alle möglichen Aufteilungen A der benötigten Bretter auf C

Die (gültige) Aufteilung A mit der geringsten summierten Länge ist das Optimum.