Containerladeprobleme gehören zu den allgemeinen Schnitt - und Packproblemen. Man kann sich leicht vorstellen, dass es prinzipiell gleichgültig ist, ob man eine vorhandene Fläche mit verschiedenen Quadern belegt, also die Grundfläche mit Rechtecken belegt, oder ob man aus einer rechteckigen Fläche diese rechteckigen Stücke herausschneidet.
Noch mehr verallgemeinert ist es auch möglich, ein lineares Problem wie die Frage, wie man aus einer größeren Anzahl langer Latten viele verschiedene kleine Latten schneiden kann, damit man möglichst wenig Verschnitt hat.
Genauso gleich sind die beiden Probleme, quaderförmige Stücke in einen Container zu packen wie aus einem Block solche Stücke herauszuschneiden. Vielleicht braucht man nicht bei diesen Blöcken auf die Standsicherheit der herausgetrennten Blöcke zu achten wie bei Kisten im Container. Sonst aber sind die Proleme gleich.
Weil das so ist, beginnen wir unsere Untersuchung bei einem ganz einfachen linearen Problem. [Es ist das "einfache" Rucksack - Problem, bei dem es darum geht, möglichst viele, möglichst schwere, möglichst große oder vielleicht möglichst wertvolle Teile in einen Rucksack zu packen, der nicht alle von ihnen fasst. In anderem Gewand ist es das Geldwechselprolem usw.] Wir betrachten eine Latte einer gegebenen Länge, aus der bestimmte kleinere Latten geschnitten werden sollen, so dass möglichst wenig Verschnitt auftritt.
Unser Container lässt sich nun mit einer einfachen Zahl beschreiben, die Stücke ebenfalls und die Bewertungsfunktion für die Güte ist auch sehr einfach: Man zählt deren Werte einfach zusammen.
Aufgabe zum Cutting - Problem
Schreiben Sie ein Programm, das Ihnen sowohl einen "Container" gegebener Länge zufällig generiert, als auch eine größere Zahl kleinerer Stücke, die in ihn hinein getan werden sollen. Untersuchen Sie mit den dabei gegebenen Wert [per Hand selbst], ob und ggf. wie der prozentuale Wert des Verschnitts von der Zahl der Stücke und von der Größenverhältnissen abhängt.