Kombinatorische Verschnittoptimierung

[seth_not@home]

gudn tach!

Gegeben sind als Ausgangsware Stangen fester Länge. Nun gilt es, aus diesen Stangen eine Vielzahl kleinerer Stangen zu schnippeln. Dabei soll möglichst geringer Verschnitt entstehen.

ich habe das jetzt so verstanden:
du hast n stangen, die alle die gleiche laenge a haben. und du willst moeglichst viele kleine stangen der laenge b, wobei b<a.

aber die loesung dafuer ist nicht kompliziert:
max_anz_stangen = n*floor(a/b)
verschnitt ist dabei schon minimal, naemlich n*(a mod b).

wahrscheinlich habe ich dich bloss falsch verstanden. was genau moechtest du?
interessant wird es eigentlich erst, wenn a und b nicht konstant sind. und sollen moeglichst viele kleine stangen hergestellt werden? oder ist vorgegeben, wieviele kleine stangen geschnippelt werden sollen und es ist nur der verschnitt zu minimieren?

prost
seth