Das dürfte eine Frage der Ganzzahligen lineare Optimierung sein. Zu minimieren ist die Anzahl der Hölzer, der Lösungsvektor gibt dann die Nummer des Holzes an, aus dem ein Brett zu sägen ist.

Der Praktiker würde wohl einwenden, dass auch mit der feinsten Säge etwa ein Millimeter pro Schnitt verlorengeht. Das macht das Problem nicht viel schwieriger, ändert aber im Beispiel schon die Lösung :)

Ergänzung nach barneys Hinweis und Muffis Codebeispiel: Wenn die Hölzer alle gleich lang sind, dann trifft es das Eindimensionale Zuschnittproblem genauer:

Quote

Das eindimensionale Zuschnittproblem (englisch one-dimensional cutting stock problem) ist ein NP-schweres ganzzahliges lineares Optimierungsproblem mit dem Ziel, eindimensionale Teile in vorgegebenen Bedarfszahlen aus möglichst wenig Stücken Material gegebener Länge zuzuschneiden.

Der Artikel verweist dann auf das Behälterproblem, und dort findet man auch eine Näherungslösung mit Laufzeit O(n*log(n)):

Quote

Sortiere die Objekte nach absteigendem Gewicht
Füge die Objekte der Reihe nach ein,
sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.
Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen

Dass man da länglich drüber theoretisieren kann, ergibt sich daraus, dass es für die "korrekten" einfachen Algorithmen wie den von Muffi pathologische Daten gibt, bei denen sie einfach zu lange brauchen. Im Code von Muffi verwende man:
Da kann man sich dann schon mal einen Kaffee holen, bis das fertig wird, und der Bildschirm scrollt dabei über mehr als 10 Meter.

Letzte Worte: Ich säge ganz gern mal im Keller und habe dabei festgestellt, dass ich meistens die zusätzliche Nebenbedingung habe, dass vom vorigen Projekt noch Rest-Bretter unterschiedlicher Länge rumliegen, die nach Möglichkeit mit verarbeitet werden sollen. Vielleicht sollte ich ja doch mal ein Programm schreiben?
Last edited: 2018-10-08 20:01:08 +0200 (CEST)