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
Algorhytmus um geringsten Holzverbrauch zu ermitteln
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
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
Das Leben ist wie ein Tennisball.
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
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
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Es gibt bestimmt "fertige" Solver für diese Problemklasse, die vermutlich heuristisch vorgehen dürften. Evtl. suchst Du einfach mal danach?
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
assert encoding_kapiert
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Sogar in PythonHyperion hat geschrieben:Es gibt bestimmt "fertige" Solver für diese Problemklasse, die vermutlich heuristisch vorgehen dürften.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Hier mal ein erster Versuch von mir:
https://gist.github.com/anonymous/03aa92a58e17bcb41f64
https://gist.github.com/anonymous/03aa92a58e17bcb41f64
@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:
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.
Code: Alles auswählen
needed_lumber = {5: 1, 4: 2, 3:1, 2:2}
dimensions = [10]
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.
Das Leben ist wie ein Tennisball.
@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.
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.
In dem Thread ging es ja gerade darum, dass die optimale Lösung gefunden wird.snafu hat geschrieben:@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...
Wie ich schon schrieb: Einfach alle Varianten durchprobieren, das lässt sich sehr leicht implementieren:snafu hat geschrieben:Wie gesagt: Bessere Vorschläge sind willkommen. Idealerweise mit Code.
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.
Das Leben ist wie ein Tennisball.