Wenn jetzt von einer a-Stange noch 5 Meter übrig sind, wäre es z.B. sinnvoll, eine 4,5er-Stange (b) vom nächsten "a" abzusäbeln, da ich sonst 0,5 Meter Verschnitt hätte.

Wie jetzt? Wäre es sinnvoll, damit du "nur" 0,5 Meter Verschnitt hast, oder wäre es eher nicht sinnvoll, da du sonst 0,5 Meter Verschnitt hast.

Schnippel ichs von besagter a-Stange ab, wärs nicht sinnvoll, da die 0,5 garantiert Verschnitt wären. Schnippel ichs von der nächsten (noch kompletten) a-Stange ab, hab ich zumindest noch die Chance, ohne Verschnitt auszukommen.

Das funktioniert aber nur, wenn du garantiert weißt, welche weitere Stangenlänge nach dieser 4,5-Meter-Stange noch gebraucht wird.

Wenn keinerlei weitere Stange benötigt wird, hast du 5 Meter Verschnitt von der ersten und 45,5 Meter Verschnitt von der zweiten Stange. Das ist deutlich mehr, als 0,5 Meter von der ersten und keinerlei Verschnitt von der zweiten Stange.

Du benötigst erstens schon mal zwingend alle abzuschneidenden Stangen auf einmal.
Ja, vermutlich. Oder eben Wahrscheinlichkeiten auf Basis historischer Werte...(aber das ist schon ein anderes Thema). Sagen wir einfach,  Anzahl und Länge der einzelnen b-Stangen sind bekannt.

Das ist zwingend notwendig. Du kennst sowohl Anzahl als auch Länge aller abzuschneidender Stangen.

Wenn das nicht so wäre, sondern du aus laufender Produktionsanforderung die Aufgabe hast, aus den A-Stangen unter Vermeidung von überflüssig viel Verschnitt, aber mit unbegrenzter Zahl von A-Stangen beliebig viele B-Stangen zu generieren, würde ich Längenklassen bilden.

Eine A-Stange kriegt dann einfach ein Label "Aufteilen in X Stücke der Länge Y", und jede Stange, die in diese Längenklasse fällt, wird dann halt von der (angefangenen oder neu anzufangenden) A-Stange abgeschnitten. Bei 50-Meter-Stangen würde beispielsweise eine Längenklasse 50 bis 100 cm existieren, d.h. es würden maximal 50 Stangen abschneidbar sein, und maximal wären 49 cm Verschnitt.

Klar, wenn du historische Daten der typischen Längenverteilung hast, kannst du natürlich auch eine durchschnittliche Tagesproduktion analysieren und ermitteln, dass ein 5,0-Meter-Rest wahrscheinlich noch für ein 4,99-Meter-Stück gebraucht wird, weshalb das jetzt benötigte 4,5-Meter-Stück lieber von einer neuen A-Stange geschnitten wird.

Andererseits: Hast du denn unbegrenzt Nachschub? Doch wohl eher nicht. Und unbegrenzt Lagerkapazität für angeschnittene Stangen auch nicht. Und unbegrenzt Zeit, eine irgendwann früher angebrochene Stange, die jetzt gerade exakt ohne Verschnitt passen würde, wiederzufinden, auch nicht.

Das wiederum bedeutet: Du mußt erstmal definieren, was für dich optimal denn überhaupt bedeutet?
Das wissen wir schon. Optimal = minimaler Verschnitt.

Wie gesagt, "minimaler Verschnitt" ist nicht ausreichend. Meine beiden Beispiele haben jeweils exakt 4,0 Meter Verschnitt übrig, weniger geht nicht. Die Optimierungsaufgabe benötigt weitere Regeln, wie beispielsweise "Minimale Anzahl von A-Stangen" oder "Möglichst große Reststücke".

Und wenn wir das Beispiel noch etwas modifizieren, und statt 2x 3 Metern einfach 2x 4 Meter abschneiden, dann bleiben entweder 1x 2 Meter Rest, oder 2x 1 Meter.
Auch hier ganz klar: 1x2 Meter ist IN JEDEM FALLE besser als 2x1 Meter. Logisch, oder?

Nein, das ist nicht unbedingt logisch. Es ergibt sich erst aus deinen weiteren, zu definierenden Bedingungen.

Angenommen, es werden sowieso nur Stangenlängen von 5 und 4 Metern benötigt, der Müllcontainer hat aber nur Platz für maximal 1,50 Meter lange Stangen, dann müßtest du die 2-Meter-Reste vor der Entsorgung nochmal durchschneiden. Deine "logische" Optimierung würde also in Wirklichkeit eine Verschlechterung sein, weil die Säge einen Schnitt mehr machen müßte und somit stärker abgenutzt wird.

Das ist richtig. In der Praxis müsste man praktisch eine Müll-Grenze definieren, also eine Länge, die 100%ig nicht mehr zu gebrauchen ist. Für meinen Fall ist das aber unerheblich. Hier ist das Ziel immer, möglichst viele a-Stangen komplett und ohne jeglichen Verschnitt aufzubrauchen.

Wie oben erwähnt: Es ist sicherlich möglich, eine Statistik aufzustellen mit den benötigten Längen aller zu produzierenden Abschnitte. Und diese Abschnitte, sofern sie denn in unendlicher Zahl benötigt werden, lassen sich sicherlich ziemlich optimal so verteilen, dass die verfügbaren Stangen optimal genutzt werden. Aber eben nur, wenn die Randbedingungen und Optimierungsforderungen vollständig bekannt sind.

Hallo Daniel,

Das funktioniert allerdings nur bei ganzzahligen Gewichten.

Hm das bringt mich jetzt zum Nachdenken. Ich kann diese Aussage nicht widerlegen, aber mein Gefühl sagt mir, dass die Gewichte auch reelle Größen sein könnten. Also n ist die Anzahl der Gegenstände und m ist die Größe des Rucksacks, die hochiteriert wird. m könnte doch eine Disktretisierung eines von mir aus pi großen Rucksacks sein. Man iteriert über diese Diskretisierung. Die Summe der betrachteten Gegenstände (eine reelle Zahl also) muss <= m sein, damit sie in den Rucksack passen und das ist ja kein Problem.

Also wenn überhaupt, dann müsste der Rucksack und nicht die Gewichte ganzzahling teilbar sein. Kann die Disktretisierung unter Umständen eine optimale Lösung verhindern? Vielleicht muss sie eine Bedingung erfüllen, wie z.B. dass die Schrittlänge zwischen den Größen kleiner sein muss, als das kleinste Gewicht.

Aber mal abgesehen davon, dass es uns Informatikern Spaß macht sich auch die letzten Nuancen zu überlegen, ist für das vom OP gestellte Optimierungsproblem eine centimeterweise Iterierung über die Länge der a-Stangen sicherlich ausreichend. :)

Viele Grüße,
Cruz