nicht angemeldet
Nehmen wir ein Beispielt:
a = 50 Meter
b = 1 - 30 MeterWenn 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.
Die verschiedenen b-Stangen sind zwar in Ihrer jeweiligen Länge bekannt, aber eben nicht die Reihenfolge, mit der sie von den a-Stangen abgeschnitten werden. Das gilt es zu ermitteln.
Es gibt keine Lösung in der Form, dass du einfach nur die Länge der aktuellen Stange in eine Funktion reintust, und als Antwort die Lösung "Abschneiden von Stange X" erhälst.
Du benötigst erstens schon mal zwingend alle abzuschneidenden Stangen auf einmal.
Weiterhin wird der Algorithmus ein "Probieralgorithmus" sein, d.h. er wird Annahmen treffen und testweise Lösungen ermitteln, solange bis er ein Optimum gefunden hat.
Das wiederum bedeutet: Du mußt erstmal definieren, was für dich optimal denn überhaupt bedeutet?
Bei nur einer einzigen A-Stange hast du kein Optimierungsproblem. Der Rest von A bleibt eben übrig - Pech.
Aber schon bei zwei A-Stangen ist die Frage, was du als optimal beim Verschnitt betrachtest.
Angenommen, die A-Stange ist 10 Meter lang (zwei Stück also 20 lfd Meter). Jetzt willst du folgende Stücke schneiden:
2x 5 Meter
2x 3 Meter
Mögliche Ergebnisse:
Stange 1 wird komplett aufgebraucht, Stange 2 hinterläßt einen Rest von 4 Metern. Oder beide Stangen werden zu jeweils 8 Metern genutzt und hinterlassen jeweils 2 Meter Rest.
Die Frage ist eben: Kann man mit einem einzigen 4-Meter-Rest mehr anfangen, als mit zwei 2-Meter-Resten? Was ist wünschenswerter?
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.
Wenn nun aber sowohl der 2-Meter-Rest, als auch der 1-Meter-Rest im Müll landen würden - ist es dann notwendig, den Verschnitt bis ins letzte zu optimieren?