Sortieren und Einsetzen verständlich erklärt

Beim Kofferpacken kommen die großen Sachen zuerst hinein, der Kleinkram füllt die Lücken. Bei Paketen in Containern ist es ähnlich: In den Beispielen dieser Seite verändert die Reihenfolge der Pakete die Containerzahl mehr als der Wechsel zwischen den beiden besseren Regeln, wohin das nächste kommt. Bei kleinen Paketen (bis 200 Stück) bringt das Sortieren dagegen wenig.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Das Bild: Koffer und Umzugskisten

Sie packen einen Koffer. Wer zuerst Schuhe und dicken Pullover hineinlegt, findet am Ende für Socken und Ladekabel noch Platz in den Lücken. Wer die Socken zuerst breit verteilt, kann die Schuhe zuletzt nicht mehr hineindrücken, obwohl der Koffer als Ganzes groß genug wäre.

Beim Umzug ist es ähnlich, nur mit vielen gleich großen Kisten. In der Logistik heißen sie Container und die Sachen Pakete; so nennen wir sie von nun an. Jeder Container fasst gleich viel, die Pakete sind verschieden groß, nur ihre Größe zählt. Gesucht ist die Packung mit möglichst wenigen Containern.

Zwei Entscheidungen legen die Packung fest: in welcher Reihenfolge Sie die Pakete nehmen und in welchen Container das nächste eingesetzt wird, wenn in mehrere noch Platz ist.

Warum passiert das?

Die Regel entscheidet nur über das, was schon in den Containern liegt: Sie sucht für das nächste Paket eine Lücke. Wie groß dieses Paket ist, bestimmt die Reihenfolge. Eine naheliegende Erklärung, die das Beispiel unten vorrechnet, aber nicht allgemein gemessen ist: Kommt ein großes Paket spät, kann keine Lücke mehr groß genug sein, und es öffnet einen neuen Container. Kommen die großen früh, bekommt jedes einen eigenen, und die kleinen füllen später die Reste daneben.

Zwei vernünftige Regeln lauten: den ersten Container nehmen, in den das Paket passt (First Fit, englisch für „der Erste, der passt“), oder den, in dem danach am wenigsten Platz bleibt (Best Fit, „der Passendste“). Beide sehen alle offenen Container an und wählen nur verschieden, wenn das Paket in mehrere passt; schon deshalb ist ihr Spielraum klein. Wie klein, zeigen die Zahlen unten.

Ein Beispiel mit zwölf Paketen

Nehmen wir zwölf Pakete mit diesen Größen, in der Reihenfolge, in der sie geliefert werden: 42, 23, 19, 44, 30, 35, 47, 50, 51, 53, 51 und 14. Ein Container fasst 100. Zusammen füllen die Pakete mehr als vier Container, also braucht jede Packung mindestens 5.

Zuerst kommt jedes Paket in der Lieferreihenfolge in den ersten Container, in dem noch Platz ist: 42, 23 und 19 in den ersten, 44 und 30 in den zweiten, 35 und 47 in den dritten. Nun folgen 50, 51, 53 und 51. Keine zwei davon passen zusammen in einen Container, denn schon die beiden kleinsten, 50 und 51, ergeben mehr als 100, und in den ersten drei Containern ist für keines noch Platz. Jedes öffnet also einen eigenen Container, und diese vier sind nur etwa halb gefüllt. Die 14 passt noch in den ersten. Ergebnis: 7 Container.

Nun dieselben Pakete, größte zuerst: 53, 51, 51, 50, 47, 44, 42, 35, 30, 23, 19, 14. Die vier großen öffnen je einen Container. 47, 44 und 42 füllen die Lücken neben 53, 51 und 51, 35 und 14 die neben 50, und 30, 23 und 19 ergeben einen fünften Container. Ergebnis: 5 Container, und weniger geht nicht. Die Regel blieb gleich, nur die Reihenfolge änderte sich; das sparte zwei Container.

Wechselt man in der Lieferreihenfolge zur Regel „der Passendste“, bleibt es bei 7. Eine dritte, schwächere Regel sieht nur den zuletzt geöffneten Container an (Next Fit, „der Nächste“) und kann Lücken älterer Container nie nutzen; im Beispiel bleibt es mit ihr auch nach dem Sortieren bei 7. Sie dient nur als Vergleichsmaßstab und zählt beim Vergleich von Reihenfolge und Regelwechsel nicht mit.

Was hilft?

Wer alle Pakete vorher kennt, sortiert sie nach der Größe und setzt die größten zuerst, jedes in den ersten Container, in dem es passt. Das braucht keine neue Regel, nur eine Sortierung. Wer jedes Paket sofort einsetzen muss, kann nicht sortieren; dazu sagt diese Seite nichts.

Ein Maßstab zeigt, wie gut eine Packung ist: die Summe aller Größen durch die Containergröße, aufgerundet (die Volumenschranke, hier Untergrenze genannt). Keine Packung kommt mit weniger Containern aus. Im Beispiel ergibt das 5. Liegt Ihr Ergebnis darüber, bleibt offen, ob es besser ginge: Die Untergrenze zählt nur die Gesamtgröße und rechnet nicht ein, dass sich große Pakete keinen Container teilen.

Was die Messungen zeigen

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie rechnet zwei Beispiele wie das obige und erfundene Ladungen: zweihundert für jede Kombination aus vier Größenbereichen der Pakete und vier Paketzahlen, zusammen mehr als dreitausend. Ein fester Startwert des Zufalls sorgt dafür, dass jeder Lauf dieselben liefert. Eine Kombination heißt hier Messreihe; die Zahlen sind Durchschnitte über ihre Ladungen.

• Sortieren schlägt Regelwechsel. Bei großen Paketen und zweihundert Stück spart der Wechsel zwischen den beiden besseren Regeln gegenüber der Lieferreihenfolge im Durchschnitt knapp zwei Container, das Sortieren knapp sieben.
• Nach dem Sortieren sind die beiden besseren Regeln so gut wie gleich: Nur in einer von rund dreitausend Ladungen brauchten sie verschieden viele Container.
• Sortieren hilft nicht überall. Bei kleinen Paketen (höchstens ein Viertel eines Containers) spart es bis zu zweihundert Stück im Durchschnitt weniger als einen Container gegenüber der Lieferreihenfolge mit der Regel „erster Passender“. Der Gewinn wächst mit der Paketzahl; über zweihundert Stück hinaus hat die Demo nichts gemessen.

Häufige Missverständnisse

• „Größte zuerst ist das Beste, was man erreichen kann.“ Nein: Es gibt Ladungen, bei denen „größte zuerst“ elf Container braucht, obwohl neun genügen. Sie sind gezielt gebaut: vier Sorten Pakete, die sich nur in einer bestimmten Kombination zu ganz vollen Containern fügen, während „größte zuerst“ Lücken lässt, die gerade eben zu klein sind. Der zweite Teil rechnet sie vor.
• „Liegt meine Packung über der Untergrenze, war sie schlecht.“ Nein: Die Untergrenze kann niedriger sein als das wirkliche Minimum. Bei großen Paketen lag in den Messungen selbst die sortierte Packung bei den beiden größten Paketzahlen in der Mehrzahl der Fälle um zwei oder mehr Container darüber; die Untergrenze ist dort schwach.

Woran Sie das im Betrieb erkennen: Hinweise, keine Beweise

• Im Beispiel waren die letzten vier Container nur etwa halb gefüllt und enthielten je ein einziges großes Paket, die ersten gut gefüllt. Ein solches Bild bei Ihnen spricht dafür, dass die Reihenfolge der Hebel ist.
• Gegenprobe: Rechnen Sie dieselbe Ladung einmal in Ankunftsreihenfolge und einmal sortiert durch. Unterscheiden sich die Containerzahlen, ist die Reihenfolge Ihr Hebel; bleiben sie gleich, bringt das Sortieren bei dieser Ladung nichts.

Wie ernst sind die Rechnungen zu nehmen?

Alle Zahlen stammen aus zwei Beispielen und aus erfundenen, per Zufall erzeugten Ladungen mit gleichmäßig verteilten Paketgrößen. Praxisdaten kommen nicht vor. Jedes Paket hat nur eine Größe; Gewicht neben der Größe und Pakete, die man sofort einsetzen muss, bleiben außen vor. Mit anderen Zufallsmengen ändern sich die Durchschnitte etwas, und eine einzelne Messreihe ist kein Gesetz. Sie zeigen, wie sich die Regeln zueinander verhalten, nicht, wie Sie packen.

Was Sie mitnehmen

• Große zuerst, die kleinen in die Lücken: Das braucht keine neue Regel, nur eine Sortierung, solange Sie alle Pakete vorher kennen.
• In diesen Messungen verändert die Reihenfolge die Zahl der Container mehr als der Wechsel zwischen den beiden besseren Regeln.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Gegeben sind \(n\) Pakete mit ganzzahligen Größen \(s_1, \dots, s_n\), \(1 \le s_i \le C\), und Container der Kapazität \(C\). Alle Pakete sind vorab bekannt; es gibt eine Größe je Paket und keine Geometrie. Gesucht ist die kleinste Zahl \(\mathrm{OPT}\) von Containern, auf die sich die Pakete aufteilen lassen. Die Demo packt nicht optimal, sondern über einen Dekodierer: Eine Reihenfolge \(\pi\) der Pakete und eine Regel bestimmen die Packung, indem die Pakete nacheinander gesetzt werden. Passt ein Paket nirgends hin, öffnet es einen neuen Container.

• Regeln: Next Fit prüft nur den zuletzt geöffneten Container, First Fit den Container mit der kleinsten Nummer, in dem das Paket noch passt, Best Fit unter den passenden den mit dem kleinsten freien Platz danach (Gleichstand: der früher geöffnete).
• Reihenfolgen: wie geliefert, größte zuerst (Gleichstand: kleinere Nummer zuerst) oder zufällig mit fester Startzahl. FFD ist First Fit mit größten zuerst, BFD Best Fit mit größten zuerst.
• Handbeispiele: zwei feste Mengen von je zwölf Paketen, Kapazität 100; das exakte Optimum rechnet die Demo bis zu zwölf Paketen per Teilmengen-DP (lexikographisch kleinstes Paar aus Containerzahl und Füllung des letzten Containers).
• Messraster: vier Größenbereiche (kleine Teile 1 bis 25 %, mittlere 10 bis 50 %, große 20 bis 80 %, breite 1 bis 90 % der Kapazität) × vier Paketzahlen (20, 50, 100, 200) × 200 feste Instanzen je Zelle, also 16 Zellen und 3200 Instanzen; Kapazität 1000, Größen gleichverteilt und ganzzahlig. Alle Zahlen unten stammen aus diesen Instanzen und den zwei Handbeispielen.
• Maßstab im Raster: die Schranke \(L_2\), weil das Optimum für so viele Pakete nicht berechnet wird. „Container über \(L_2\)“ ist der Mittelwert über die 200 Instanzen einer Zelle von (Containerzahl des Verfahrens minus \(L_2\)).

Die Formeln

Volumenschranke: Jeder Container fasst höchstens \(C\), also braucht jede Packung mindestens so viele Container, wie die Summe der Größen aufgerundet durch \(C\) ergibt.

\[L_1 = \left\lceil \tfrac{1}{C} \sum_i s_i \right\rceil \le \mathrm{OPT}\]

Schranke \(L_2\) (Martello und Toth). Für \(\alpha \ge 0\) sei \(J_1 = \{ s_i > C - \alpha \}\), \(J_2 = \{ C - \alpha \ge s_i > C/2 \}\) und \(J_3 = \{ C/2 \ge s_i \ge \alpha \}\). Pakete aus \(J_1 \cup J_2\) brauchen je einen eigenen Container, denn für \(\alpha \le C/2\) sind sie alle größer als \(C/2\). Die Pakete aus \(J_3\) füllen zuerst den freien Platz der \(J_2\)-Container; was darüber hinausgeht, braucht weitere Container:

\[L(\alpha) = |J_1| + |J_2| + \max\!\left(0, \left\lceil \frac{\sum_{J_3} s_i - (|J_2|\,C - \sum_{J_2} s_i)}{C} \right\rceil\right), \qquad L_2 = \max_\alpha L(\alpha).\]

Es genügt \(\alpha \in \{0\} \cup \{ s_i : s_i \le C/2 \}\), und es gilt \(L_1 \le L_2 \le \mathrm{OPT}\). Ein Test der Demo rechnet \(L_2\) unabhängig über alle ganzzahligen \(\alpha\) nach und prüft die Ordnung FFD \(\ge\) OPT \(\ge L_2 \ge L_1\) an kleinen Instanzen mit exaktem Optimum.

Gütegarantie für FFD aus der Literatur, so wie die README sie nennt: Johnson u. a. zeigten \(\mathrm{FFD} \le \tfrac{11}{9}\,\mathrm{OPT} + 4\), Dósa die schärfere Form mit einer Konstante, die bestmöglich sein soll:

\[\mathrm{FFD} \le \tfrac{11}{9}\,\mathrm{OPT} + \tfrac{6}{9}\]

Die Demo prüft die zweite Schranke an kleinen Instanzen gegen das exakte Optimum; die Originale wurden laut README nicht gelesen (siehe Quellen).

Zwei durchgerechnete Beispiele

Beispiel 1 (zwölf Pakete, Summe 459, Kapazität 100): \(L_1 = \lceil 459/100 \rceil = 5\), das Optimum ist ebenfalls 5. Rechnung dieser Seite mit dem Kern der Demo, Pakete in Lieferreihenfolge und First Fit: Die Pakete 42, 23, 19 füllen den ersten Container (84), 44 und 30 den zweiten (74), 35 und 47 den dritten (82). Danach kommen 50, 51, 53 und 51; keines passt in einen der drei Container (freie Plätze 16, 26 und 18), jedes öffnet einen neuen. Das letzte Paket 14 passt in den ersten Container (98). Das sind 7 Container, vier davon mit nur einem Paket. Best Fit setzt jedes Paket an denselben Platz. Die Containerzahl prüft ein Test der Demo; die Füllungen hat diese Seite selbst nachgerechnet.

Größte zuerst, First Fit: 53 + 47, 51 + 44, 51 + 42, 50 + 35 + 14 und 30 + 23 + 19 (diese Gruppen prüft ein Test der Demo); die Füllungen 100, 95, 93, 99 und 72 sind eine Rechnung dieser Seite. Das sind 5 Container, also gleich der Schranke.

Containerzahl	Next Fit	First Fit	Best Fit
Beispiel 1, wie geliefert	7	7	7
Beispiel 1, größte zuerst	7	5	5
Beispiel 2 (Summe 467, Optimum 5), wie geliefert	7	6	6
Beispiel 2, größte zuerst	7	5	5

Eine Paketmenge, bei der auch FFD das Optimum verfehlt (Kapazität 1000): 6 Pakete der Größe 502, 6 der Größe 254, 6 der Größe 252 und 12 der Größe 246. Die Summe ist 9000, also ist \(L_1 = 9\). Eine Packung mit 9 Containern: sechsmal 502 + 252 + 246 und dreimal 254 + 254 + 246 + 246, jeweils genau 1000 (der Test der Demo prüft diese Packung auf Zulässigkeit). Das Optimum ist also 9. FFD setzt die sechs 502er in sechs Container und legt je ein 254er dazu (Füllung 756, freie 244). Weder ein 252er noch ein 246er passt in diese Lücken. Drei 252er füllen einen Container (756), zwei Container nehmen die sechs; je vier 246er füllen einen Container (984), drei Container nehmen die zwölf. Zusammen 6 + 2 + 3 = 11 Container. Der Test prüft, dass auch BFD 11 braucht und dass bei Vielfachen der Menge (Faktor \(k\) = 1, 2 und 3) \(L_1 = 9k\) und FFD \(11k\) Container ergeben. Die Lücke von 244 ist um 2 zu klein für ein 246er-Paket.

Warum die Reihenfolge so viel ausmacht

Das ist eine Deutung dieser Seite, keine Messung. Ein Paket über der halben Kapazität teilt sich keinen Container mit einem zweiten solchen Paket; \(L_2\) beruht darauf. Ob die Lücken neben diesen Paketen mit kleinen Paketen gefüllt werden, hängt davon ab, wann die großen eintreffen: Kommen sie zuletzt, sind die offenen Container schon mit mittleren Paketen belegt, und jedes große öffnet einen neuen (so im Beispiel 1 bei Lieferreihenfolge). Kommen sie zuerst, entstehen die Lücken neben ihnen früh, und die späteren Pakete füllen sie.

First Fit und Best Fit prüfen beide alle offenen Container. Sie unterscheiden sich nur, wenn in mindestens zwei Container das Paket passt, und dann nur in der Wahl unter ihnen. Die Reihenfolge legt dagegen fest, welche Pakete aufeinandertreffen. Warum FFD und BFD in 15 von 16 Zellen dieselben Mittelwerte haben, nennt die README nicht; die Frage ist in der Messreihe nicht untersucht.

Das Urteil der App zur Kernfrage zählt über das ganze 3 × 3-Raster aus Reihenfolge und Regel: Es vergleicht den größten Unterschied zwischen First Fit und Best Fit in einer Zeile mit dem größten Unterschied zwischen den Reihenfolgen in der Spalte First Fit oder Best Fit. Next Fit steht gesondert, weil es nur den letzten Container prüft. Beim Beispiel 1 ist der Unterschied zwischen den Reihenfolgen größer, bei jeder Startzahl der Zufallsreihenfolge von 0 bis 999 (Rechnung dieser Seite). Beim Beispiel 2 gilt das nicht für jede Startzahl; die README vermerkt es, und die Rechnung dieser Seite über dieselben Startzahlen findet 87 von 1000, bei denen der Unterschied zwischen den Reihenfolgen nicht größer ist als der zwischen den Regeln. Auch der Satz „ein Wechsel zwischen First Fit und Best Fit in keiner Zeile“ gilt für die voreingestellte Startzahl 7: Über die Startzahlen 0 bis 999 unterscheiden sich First Fit und Best Fit beim Beispiel 1 bei 13 von 1000 in mindestens einer Zeile des Rasters (der Zufallszeile), beim Beispiel 2 bei 143 von 1000.

Befunde

Die Zahlen stammen aus der README der Demo und ihren Tests (tests/test_claims.py, tests/test_algorithm.py, tests/test_oracle_sortieren_einsetzen.py). Alles ist Messung an den zwei Handbeispielen und an erfundenen Zufallsinstanzen mit festen Startzahlen (je 200 pro Zelle, Kapazität 1000, gleichverteilte Größen), nicht an Praxisdaten.

Frage	Befund und Voraussetzung
Beispiel 1 (zwölf Pakete, Summe 459, Volumenschranke 5, Optimum 5): Regel oder Reihenfolge?	Wie geliefert brauchen Next Fit, First Fit und Best Fit 7, 7, 7 Container; größte zuerst 7, 5, 5. Die Reihenfolge verändert die Containerzahl um 2, ein Wechsel zwischen First Fit und Best Fit in keiner Zeile (Raster der App bei Startzahl 7).
Beispiel 2 (Summe 467, Optimum 5)	Wie geliefert 7, 6, 6, größte zuerst 7, 5, 5 (Next Fit, First Fit, Best Fit). Nicht bei jeder Startzahl der Zufallsreihenfolge ist der Einfluss der Reihenfolge größer als der der Regel.
Wie weit hilft Sortieren bei großen Teilen und 200 Paketen?	Container über \(L_2\) im Mittel: Next Fit 35,32, First Fit 7,54, Best Fit 5,67, FFD 0,72, BFD 0,72 (200 Instanzen). Rechnung dieser Seite aus den ungerundeten Summen: Der Wechsel auf Best Fit spart gegenüber First Fit in Lieferreihenfolge im Mittel 1,88 Container, das Sortieren (FFD) 6,83.
Unterscheiden sich FFD und BFD?	In 1 von 3200 Instanzen (mit anderen Startzahlen können es einige mehr sein); die Mittelwerte sind in 15 von 16 Zellen gleich.
Best Fit gegen First Fit, beide in Lieferreihenfolge	Im Mittel über die 200 Instanzen einer Zelle braucht Best Fit in 16 von 16 Zellen höchstens so viele Container wie First Fit und in 13 Zellen weniger (einzelne Instanzen können anders ausfallen).
Wie viel spart Sortieren gegenüber First Fit in Lieferreihenfolge?	Im Mittel in 7 von 16 Zellen mindestens einen Container; in den anderen neun nicht (kleine Teile, mittlere Teile bis n = 100, große und breite Teile mit n = 20). In den 13 Zellen, in denen Best Fit besser ist als First Fit, ist der Gewinn durch Sortieren mindestens 3,6-mal so groß wie der durch den Wechsel auf Best Fit (kleinster Wert bei großen Teilen mit n = 200).
Trifft FFD die Schranke \(L_2\)?	In 15 von 16 Zellen nicht in allen Instanzen; nur bei kleinen Teilen mit n = 50 in allen 200.
Gibt es Pakete, bei denen auch FFD das Optimum verfehlt?	Ja: 502, 254, 252 und 246 (Kapazität 1000; 6, 6, 6 und 12 Stück): FFD braucht 11 Container, das Optimum ist 9 (explizite Packung mit 9 Containern im Test der Demo).

Trifft FFD die Volumenschranke \(L_1\)? Anteil der Instanzen je Zelle, Paketzahl \(n\) = 20 / 50 / 100 / 200:

Größenbereich	n = 20	n = 50	n = 100	n = 200
kleine Teile	99,0 %	100,0 %	97,0 %	96,0 %
mittlere Teile	79,5 %	63,0 %	33,0 %	1,0 %
große Teile	18,0 %	6,5 %	1,5 %	0,0 %
breite Teile	34,0 %	17,5 %	15,5 %	9,0 %

Die Hypothese „FFD trifft \(L_1\) fast immer“ gilt nur bei kleinen Teilen. Rechnung dieser Seite zur Schwäche von \(L_1\) bei großen Teilen: In wie vielen der 200 Instanzen liegt FFD mindestens 2 Container über \(L_1\)? Bei n = 20 / 50 / 100 / 200 sind es 61 / 119 / 139 / 185. Da FFD im Mittel nur 0,72 über \(L_2\) liegt (n = 200), liegt \(L_2\) dort im Mittel 3,75 Container über \(L_1\) (Rechnung dieser Seite, große Teile mit n = 200); eine Packung über \(L_1\) ist also noch kein Hinweis auf eine schlechte Packung.

Was die Messung zeigt

• Belegt: In den 13 Zellen, in denen Best Fit im Mittel besser ist als First Fit, bringt Sortieren mindestens 3,6-mal so viel wie der Regelwechsel; in den Handbeispielen wirkt die Reihenfolge stärker als die Regel (Beispiel 2 nicht bei jeder Startzahl). Das ist eine Aussage über Mittelwerte von 200 Instanzen je Zelle und über First Fit gegen Best Fit; Next Fit ist darin nicht verglichen.
• Belegt nicht über die Zelle hinaus: Für kleine Teile, für mittlere Teile bis n = 100 und für große und breite Teile mit n = 20 spart Sortieren im Mittel weniger als einen Container. Bei kleinen Teilen wächst der Gewinn (First Fit minus FFD, Rechnung dieser Seite aus den vorberechneten Summen) mit der Paketzahl: 0,04 / 0,045 / 0,095 / 0,195 bei n = 20 / 50 / 100 / 200; über n = 200 hinaus ist nichts gemessen, die Aussage „bringt wenig“ gilt also nur bis dahin. Die Schwelle „mindestens ein Container“ legt die App fest (GAIN_SCHWELLE); sie ist kein statistisches Kriterium.
• Nur Mittelwerte und Anteile: Die Demo zeigt zu keiner Zelle eine Streuung oder ein Vertrauensintervall. „Eine einzelne Zelle ist kein Gesetz“, sagt die README, und mit anderen Startzahlen ändern sich die Mittelwerte etwas.
• Der Maßstab ist \(L_2\), nicht das Optimum: Wo \(L_2\) unter dem Optimum liegt, ist der gemessene Abstand zu groß. Ein Wert „Container über \(L_2\)“ größer als null zeigt also nicht, dass eine bessere Packung existiert.
• Die konstruierte Menge ist ein Gegenbeispiel, keine Häufigkeit: Sie zeigt, dass FFD das Optimum verfehlen kann. Wie oft das bei Zufallsmengen vorkommt, misst die Demo nicht, denn das Optimum rechnet sie nur bis zu zwölf Paketen.

Grenzen

• Verteilung und Raster: Alle Aussagen gelten für gleichverteilte Paketgrößen in vier Bereichen, vier Paketzahlen und eine Größe je Paket. Mit zwei Grenzen gleichzeitig (Volumen und Gewicht) ist die Frage „wonach sortiert man?“ offen und nicht Gegenstand der Demo.
• Keine Praxisdaten: Das Raster sagt nichts über reale Ladungen. Die Zufallsgrößen sind erfunden und werden mit festen Startzahlen erzeugt; die zwei Handbeispiele sind feste Listen.
• Optimum nur klein: Das Optimum rechnet die Demo nur bis zu zwölf Pakete. Im Raster steht deshalb der Abstand zur Schranke \(L_2\).
• Offline: Alle Pakete sind vor dem Packen bekannt. Für Pakete, die einzeln und ohne Kenntnis der späteren eintreffen, gilt das nicht (Online-Packen).
• Next Fit ist ein Maßstab: Er steht für „nur den letzten Container prüfen“ und ist kein Vorschlag.
• Gütegarantien: Die Werte \(\tfrac{11}{9}\,\mathrm{OPT} + 4\) und \(\tfrac{11}{9}\,\mathrm{OPT} + \tfrac{6}{9}\) stammen aus Suchtreffern und Sekundärquellen; die Originale wurden nicht gelesen.
• Bedienung: Die README vermerkt, dass die App im Browser auf Desktopbreite bedient wurde; auf Telefonbreite wurde nur das Layout geprüft, nicht auf einem echten Touch-Gerät.

Erweiterungen und Verweise

Wer die Pakete nicht vorab kennt, packt online; das behandeln die Seiten zu Online-Algorithmen. Mit Geometrie packt die dreidimensionale Fall-Demo pack_demo; die Demo hier erklärt den einfachsten Fall davor, eine Größe je Paket. Weitere Demos zum Packen mit Schranken, zwei Grenzen, Rechtecken und Quadern stehen auf der Seite Packen: Reihenfolge und Platzierungsregel. Bewusst nicht umgesetzt sind ein PDF-Export des Packplans und ein Optimum über zwölf Pakete (das bräuchte ein Modell mit Spaltenerzeugung oder Arc-Flow).

Quellen

• Quelltext, Dokumentation und Tests der Demo: github.com/sebastian-hanisch/sortieren-einsetzen-demo.
• Johnson, Demers, Ullman, Garey und Graham: SIAM J. Comput. 3, 1974: Gütegarantie von FFD (nach Angabe der README).
• Dósa (2007): schärfere Gütegarantie von FFD (nach Angabe der README).
• Martello und Toth: untere Schranke \(L_2\) für das Behälterproblem (nach Angabe der README, ohne Fundstelle).

Für diese Seite wurde keine Literatur nachgeschlagen. Die Angaben zu den Gütegarantien und zur Schranke \(L_2\) stammen aus der README der Demo, die sie ihrerseits aus Suchtreffern und Sekundärquellen übernommen hat. Alle Messzahlen stammen aus der README; die Füllungen der Beispiele, die Packung der konstruierten Menge und die Zählung über die Startzahlen sind Rechnungen dieser Seite mit dem Kern der Demo.