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.
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.
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.
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.
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 hatte ich befürchtet. ;-)
Das wiederum bedeutet: Du mußt erstmal definieren, was für dich optimal denn überhaupt bedeutet?
Das wissen wir schon. Optimal = minimaler Verschnitt.
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 MeterMö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?
Natürlich in diesem Fall die 4 Meter. Damit kann man IN JEDEM FALL mehr anfangen.
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?
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?
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.
Salut
Kopfkratzer