Kombinatorische Verschnittoptimierung

[wahsaga]

hi,

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.

Meine Frage nun: Wie lassen sich derlei Aufgaben (eindimensionale Verschnittoptimierung) mathematisch am besten lösen.

Mathematisch wäre das wohl eine Extremwert-Aufgabe, wenn ich nicht alles aus Schulzeiten vergessen habe.

Ich kenne wohl Programme, die solche Aufgaben erledigen, weiß aber nicht genau, wie deren Algorithmen funktionieren.

Algorithmisch wäre vielleicht Backtracking ein passendes Stichwort.

gruß,
wahsaga