Die Untergrenze beim Packen verständlich erklärt

Eine Spedition hat ihre Wagen beladen und fragt sich: Ginge es mit einem Wagen weniger? Eine Rechnung aus der Gesamtmenge nennt eine Zahl, unter die kein Plan kommen kann. Trifft der Plan diese Zahl, ist er der beste. Liegt er darüber, bleibt die Frage offen, aus zwei ganz verschiedenen Gründen.

Zuletzt aktualisiert: 11. November 2026

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

Das Bild: ein Umzugswagen

Ein Umzugsunternehmen soll Möbel, Kartons und Kisten in Wagen laden. Jedes Stück heißt hier Paket, alle Pakete zusammen die Ladung. Jeder Wagen fasst gleich viel, und kein Paket wird auf zwei Wagen verteilt. Geladen wird nach einer einfachen Regel: das größte Paket zuerst, jedes Paket in den ersten Wagen, in dem noch Platz ist. Fachleute nennen das First Fit Decreasing, kurz FFD. Wer in welchem Wagen fährt, heißt hier Plan.

Am Ende steht eine Zahl von Wagen auf dem Hof, und es kommt die Frage: Hätte es mit weniger gereicht? Zwei Antworten sind möglich. Entweder findet jemand einen Plan mit weniger Wagen, oder jemand beweist, dass es keinen gibt. Für den Beweis dient eine Untergrenze (Fachleute sagen untere Schranke): eine Zahl, unter die kein Plan kommen kann.

Die erste Untergrenze: die Gesamtmenge

Alle Pakete zusammen brauchen eine bestimmte Menge Platz. Teilt man sie durch den Platz eines Wagens und rundet auf, ergibt sich die kleinste Wagenzahl, mit der es überhaupt gehen kann. Aufrunden muss man, weil ein Rest, der nicht mehr in die vollen Wagen passt, einen weiteren Wagen braucht.

Nehmen wir als Beispiel Wagen mit Platz für 10 Einheiten und eine Ladung aus fünf Paketen der Größen 6, 6, 6, 1 und 1. Zusammen sind das 20 Einheiten, also genau zwei volle Wagen. Läge die Summe eine Einheit höher, wären es zwei volle Wagen und ein Rest, aufgerundet also drei. Hier verlangt die Gesamtmenge mindestens zwei Wagen. Ob zwei reichen, sagt sie nicht.

Die schärfere Untergrenze: Pakete über der Hälfte

Die Gesamtmenge übersieht, dass sich Platz nicht beliebig verschieben lässt. Ein großes Paket, so nennen wir hier eines, das mehr als die Hälfte eines Wagens füllt, kann sich mit keinem anderen solchen Paket einen Wagen teilen. Im Beispiel ist jedes Paket der Größe 6 eines. Drei davon brauchen drei Wagen, obwohl die Gesamtmenge nur zwei verlangt.

Die schärfere Untergrenze zählt deshalb die großen Pakete einzeln und prüft dann, ob die übrigen in den Restplatz dieser Wagen passen. Im Beispiel bleiben in den drei Wagen je vier Einheiten frei, zusammen zwölf, und die beiden kleinen Pakete (zusammen zwei Einheiten) passen hinein. Zusätzliche Wagen braucht es nicht: drei Wagen. Zum Schluss nimmt sie das Größere aus diesem Ergebnis und der Zahl aus der Gesamtmenge, ist also nie kleiner als die erste.

Trifft der Plan die Untergrenze: der beste

Die Regel packt das Beispiel so: Der erste Wagen bekommt ein Paket der Größe 6 und die beiden kleinen, der zweite und der dritte je ein Paket der Größe 6. Das sind drei Wagen, genau die Untergrenze. Weniger als drei ist unmöglich, denn kein Plan kommt unter die Untergrenze, und dieser liegt schon darauf. Weiteres Suchen wäre vergeudet.

Liegt der Plan darüber: offen, aus zwei Gründen

Ändern wir die Ladung: fünf Pakete der Größe 4, zusammen wieder 20 Einheiten. Kein Paket füllt mehr als die Hälfte eines Wagens, die schärfere Untergrenze bleibt daher bei der Gesamtmenge, zwei Wagen. Die Regel braucht aber drei: Zwei Pakete der Größe 4 passen in einen Wagen, ein drittes nicht mehr. Der Plan liegt über der Untergrenze, der Fall ist offen.

Offen heißt nicht schlecht. Hier ist der Plan sogar der beste, denn in einen Wagen für 10 Einheiten passen höchstens zwei Pakete der Größe 4, und fünf Pakete brauchen dann mindestens drei Wagen. Die Untergrenze war zu schwach. Das ist der erste Grund.

Der zweite Grund: Die Regel verliert tatsächlich Wagen, weil es einen besseren Plan gibt, den sie nicht findet. Zu lang für eine Rechnung hier ist ein Beispiel mit zwölf Paketen: Die Regel braucht sechs Wagen, obwohl fünf reichen, beide Untergrenzen sagen fünf. Unten steht, wo man es nachrechnen kann.

Von außen sehen beide Fälle gleich aus: Der Plan liegt über der Untergrenze. Welcher vorliegt, zeigt nur die wirklich kleinste Wagenzahl, die man bei wenigen Paketen durch vollständiges Ausprobieren aller Pläne bestimmt, bei vielen mit besonderen Rechenverfahren.

Was Zufallsaufgaben zeigen

Ein Programm zum Ausprobieren im Browser, kurz Demo, hat das an erfundenen Zufallsaufgaben gemessen, je 100 für jede Mischung von Paketgrößen und jede Paketzahl (zwölf, zwanzig, dreißig); hier steht nur zwölf. (Dort heißen die Wagen Container.) In der Mischung „mittel“ ist kein Paket größer als der halbe Wagen, jede Größe im Bereich ist gleich wahrscheinlich. In der Mischung „groß“ reichen die Pakete von einem Fünftel bis zu vier Fünfteln eines Wagens, ein Teil davon ist also größer als die Hälfte.

Bei „mittel“ beweist die schärfere Untergrenze in keiner Aufgabe mehr als die Gesamtmenge. Das liegt daran, dass es ohne Pakete über der Hälfte nichts einzeln zu zählen gibt: Die Rechnung endet wieder bei der Gesamtmenge. Bei zwölf Paketen blieb der Fall in 13 von 100 Aufgaben offen; in 8 davon verlor die Regel tatsächlich Wagen, in den übrigen fünf war sie optimal.

Bei „groß“ beweist die Gesamtmenge allein bei zwölf Paketen in 38 von 100 Aufgaben, dass der Plan der beste ist, die schärfere Untergrenze beweist es in 58 weiteren. Vier Aufgaben blieben offen, und in allen vier war die Regel optimal; die Untergrenzen waren dort zu schwach.

Diese Anteile sind bei zwölf Paketen nicht stabil. Ein zweiter Satz von 100 Aufgaben derselben Art ergab bei „mittel“ nur 6 statt 8 verlorene unter 13 offenen Aufgaben, bei „groß“ zwölf statt vier offene. Gleich blieb nur eine Richtung: Bei „groß“ überwogen in beiden Sätzen die offenen Aufgaben, in denen die Regel optimal war.

Woran Sie es im Betrieb merken

Jemand fragt bei einem fertigen Plan, ob es auch mit einem Wagen weniger ginge, sei es bei Paletten im Lkw oder Kisten im Container. Rechnen Sie zuerst die Gesamtmenge geteilt durch das, was ein Wagen fasst, aufgerundet. Liegt Ihr Plan darauf, ist die Frage beantwortet. Liegt er darüber, zählen Sie die Pakete über der Hälfte: Gibt es welche, lohnt die schärfere Rechnung. Ob dann ein besserer Plan existiert, zeigt erst die kleinste mögliche Wagenzahl.

Ein Missverständnis

„Die Untergrenze sagt, wie viele Wagen reichen.“ Nein: Sie sagt, wie viele mindestens nötig sind. Bei der Ladung aus fünf Paketen der Größe 4 verlangt sie zwei Wagen, nötig sind drei.

Was Sie mitnehmen

• Trifft ein Plan eine gültige Untergrenze, ist er der beste.
• Liegt er darüber, ist der Fall offen: Die Untergrenze ist zu schwach, oder der Plan verliert Wagen.
• Welcher der beiden Fälle vorliegt, zeigt nur die kleinste mögliche Wagenzahl.

Wie ernst ist die Messung zu nehmen?

Die Demo packt erfundene Zufallsaufgaben, keine Betriebsdaten, und vergleicht nur FFD. 100 Aufgaben je Mischung sind wenig; bei zwölf Paketen verschieben sich die Anteile mit einem anderen Satz. Wie oft Ihr Betrieb auf offene Fälle stößt, sagt sie nicht.

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 keine Geometrie, nur Größen. Gesucht ist die kleinste Zahl \(\mathrm{OPT}\) von Containern, in die alle Pakete passen (Bin Packing). Verglichen wird nur FFD (First Fit Decreasing): Pakete absteigend nach Größe, bei Gleichstand die kleinere Nummer zuerst, jedes in den ersten Container mit genug Platz. Gefragt ist nicht, wie gut FFD im Mittel ist, sondern woran man im Einzelfall erkennt, dass \(\mathrm{FFD}\) schon \(\mathrm{OPT}\) ist, und was es heißt, wenn man es nicht erkennt.

• Schranken: die Volumenschranke \(L_1\) und die Schranke \(L_2\) nach Martello und Toth (so die README; die hier benutzte Form ist aus dem Gedächtnis aufgeschrieben, das Original wurde nicht gelesen). Pakete über der halben Kapazität brauchen je einen eigenen Container, die kleineren füllen deren Restplatz.
• Ausgänge je Instanz: bewiesen durch L1 (\(\mathrm{FFD} = L_1\)), bewiesen erst durch L2 (\(\mathrm{FFD} = L_2 > L_1\)), offen, FFD optimal (FFD über beiden Schranken, aber gleich dem Optimum) und offen, FFD nicht optimal (FFD über dem Optimum). Im Raster kommt ein fünfter Ausgang hinzu: nicht entschieden, wenn das Optimum nicht berechnet werden konnte.
• Handbeispiele: vier feste Mengen zu je zwölf Paketen, Kapazität 100, ein Beispiel je Ausgang.
• Raster: drei Größenbereiche (mittlere Teile 10 bis 50 %, große Teile 20 bis 80 %, breit gestreute Teile 1 bis 90 % der Kapazität) × drei Paketzahlen (12, 20, 30) × 100 feste Instanzen je Zelle, Kapazität 1000, Größen gleichverteilt und ganzzahlig. Das Optimum kommt bei 12 Paketen aus einer Teilmengen-DP über Bitmasken, bei 20 und 30 aus einem ganzzahligen Programm (Zuordnungsmodell, 10 Sekunden Zeitlimit je Aufruf). Erreicht ein Aufruf das Zeitlimit, zählt die Instanz als „nicht entschieden“.

Die Formeln

Die Volumenschranke ist die Zahl der Container, die allein der Platz verlangt:

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

Für \(L_2\) sei \(0 \le \alpha \le C/2\) eine Schwelle und \(J_1 = \{ s_i > C - \alpha \}\), \(J_2 = \{ C - \alpha \ge s_i > C/2 \}\), \(J_3 = \{ C/2 \ge s_i \ge \alpha \}\). Pakete aus \(J_1 \cup J_2\) sind größer als die halbe Kapazität und brauchen je einen eigenen Container. Korrektur dieser Seite gegenüber der Demo: Die Demo schreibt \(\alpha \ge 0\), der Code nimmt aber nur Schwellen bis \(C/2\). Für größere Schwellen stimmt die Aussage nicht: Bei drei Paketen der Größe 4 und \(C = 10\) ergäbe \(\alpha = 8\) den Wert \(L(8) = 3\), das Optimum ist aber 2 (Rechnung dieser Seite). Die Pakete aus \(J_3\) füllen zuerst den freien Platz der \(J_2\)-Container; was nicht hineinpasst, braucht zusätzliche Container. (Erläuterung dieser Seite: In den \(J_1\)-Containern bleibt weniger als \(\alpha\) frei, die \(J_3\)-Pakete sind mindestens \(\alpha\) groß, sie kommen dort also nicht in Frage.)

\[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\bigl(L_1, \max_\alpha L(\alpha)\bigr)\]

Es genügt dabei \(\alpha \in \{0\} \cup \{ s_i : s_i \le C/2 \}\). Beide Schranken liegen höchstens beim Optimum, und FFD liegt mindestens dort:

\[L_1 \le L_2 \le \mathrm{OPT} \le \mathrm{FFD}\]

Entscheidungsregel: Ist \(\mathrm{FFD} = L_1\) oder \(\mathrm{FFD} = L_2\), folgt aus der Kette \(\mathrm{FFD} = \mathrm{OPT}\): bewiesen optimal. Ist \(\mathrm{FFD}\) größer als \(L_2\), entscheiden die Schranken nicht. Dann gilt entweder \(\mathrm{OPT} = \mathrm{FFD}\) (die Schranken sind zu schwach) oder \(\mathrm{OPT} < \mathrm{FFD}\) (FFD verliert Container). Aus den Schranken allein sind beide Fälle nicht zu unterscheiden; verlässlich trennt sie nur das exakte Optimum, in der Demo bis 12 Pakete live per Teilmengen-DP, bei 20 und 30 Paketen im vorberechneten Raster per ganzzahligem Programm (Zuordnungsmodell mit einer Ja-Nein-Variablen je Paar aus Paket und Container). Ob die Schranke im zweiten Fall scharf ist (\(L_2 = \mathrm{OPT}\)) oder nicht, ändert daran nichts.

Rechnung dieser Seite (kleine Pakete): Haben alle Pakete höchstens die halbe Kapazität, sind \(J_1\) und \(J_2\) leer, weil sie nur Pakete über der halben Kapazität enthalten. Dann ist \(L(\alpha)\) höchstens die aufgerundete Summe der \(J_3\)-Pakete geteilt durch \(C\). Da \(J_3\) nur einen Teil aller Pakete enthält, ist das nicht größer als \(L_1\), und es folgt \(L_2 = L_1\). Die README nennt dasselbe Ergebnis, die Tests der Demo prüfen es an Zufallsinstanzen mit Paketen bis zur halben Kapazität.

Warum die Kette gilt

Erläuterung dieser Seite (die Demo prüft die Aussagen an Zufallsinstanzen, sie beweist sie nicht): \(\mathrm{OPT} \le \mathrm{FFD}\) gilt, weil FFD selbst eine zulässige Packung liefert und das Optimum die kleinste Zahl über alle zulässigen Packungen ist. \(L_1 \le \mathrm{OPT}\) gilt, weil jeder Container höchstens \(C\) Platz bietet: Mit weniger als \(\sum_i s_i / C\) Containern fehlte der Platz, und die Zahl der Container ist ganz. \(L_2 \le \mathrm{OPT}\) folgt für die zugelassenen Schwellen aus der Überlegung in den Formeln: Jede Packung braucht für die Pakete aus \(J_1 \cup J_2\) einen eigenen Container je Paket, und von den \(J_3\)-Paketen kann nur so viel in bereits vorhandene Container, wie dort frei ist. Der Rest braucht neue Container.

Die Kette sagt nichts darüber, wie nah \(L_2\) am Optimum liegt. Sie begrenzt nur nach unten, und FFD begrenzt nach oben. Liegen beide zusammen, ist \(\mathrm{OPT}\) eingeklemmt. Liegen sie auseinander, steht das Optimum irgendwo dazwischen, und die Schranken können nicht sagen, wo. Das ist der Kern der offenen Fälle.

Was jeder Ausgang aussagt

Ausgang	Bedingung	Aussage	Was offen bleibt
bewiesen durch L1	\(\mathrm{FFD} = L_1\)	FFD ist optimal.	nichts
bewiesen erst durch L2	\(\mathrm{FFD} = L_2 > L_1\)	FFD ist optimal; die Volumenschranke allein hätte es nicht gezeigt.	nichts
offen, FFD optimal	\(\mathrm{FFD} > L_2\), \(\mathrm{OPT} = \mathrm{FFD}\)	FFD ist optimal, die Schranken sind zu schwach.	nur der Beweis über die Schranken
offen, FFD nicht optimal	\(\mathrm{FFD} > L_2\), \(\mathrm{OPT} < \mathrm{FFD}\)	FFD verliert mindestens einen Container.	ob \(L_2\) scharf ist, hängt am Einzelfall
nicht entschieden (nur im Raster)	\(\mathrm{FFD} > L_2\), Optimum nicht bestimmt, weil ein Aufruf das Zeitlimit von 10 Sekunden erreichte	keine Aussage über FFD.	alles

Die ersten beiden Zeilen sind Beweise, die beiden mittleren sind Feststellungen, die ein exaktes Optimum voraussetzen, die letzte ist eine ehrliche Lücke der Messung. Die Ausgänge sind je Instanz eindeutig, aber nicht je Verfahren: Eine andere Packregel kann dieselbe Instanz in einen anderen Ausgang bringen, weil nur \(\mathrm{FFD}\) in die Einordnung eingeht, nicht \(\mathrm{OPT}\) oder die Schranken.

Durchgerechnet

Die vier Handbeispiele der Demo (zwölf Pakete, Kapazität 100, je ein Ausgang):

Beispiel	Summe	FFD	\(L_1\)	\(L_2\)	Optimum	Ausgang
1	613	7	7	7	7	bewiesen durch L1
2	834	11	9	11	11	bewiesen erst durch L2
3	498	6	5	5	6	offen, FFD optimal
4	496	6	5	5	5	offen, FFD nicht optimal

Beispiel 2 zeigt, was die schärfere Schranke leistet: Die Summe 834 verlangt nach \(L_1\) nur 9 Container, aber die großen Pakete erzwingen 11, und FFD trifft diese Zahl. Beispiel 3 zeigt eine zu schwache Schranke: \(\lceil 498/100 \rceil = 5\), und fünf Container fassen zwar 500, das Optimum ist aber 6, also auch FFD. Beispiel 4 hat dieselbe Schranke 5, doch FFD braucht 6 und das Optimum ist 5: Hier verliert FFD einen Container, die Schranke ist scharf. An den Schranken allein sind Beispiel 3 und 4 nicht zu unterscheiden.

Befunde

Alle Zahlen stehen in der README der Demo und sind Messungen an erfundenen Zufallsinstanzen mit festen Startzahlen: je Zelle 100 Instanzen, Kapazität 1000, Größen gleichverteilt im genannten Bereich. Sie gelten für FFD und die Schranken \(L_1\), \(L_2\), nicht für andere Verfahren, andere Verteilungen oder Praxisdaten. „Nicht entschieden“ zählt die Instanzen, bei denen ein Aufruf des ganzzahligen Programms (je geprüfter Containerzahl) das Zeitlimit von 10 Sekunden erreicht hat und kein Optimum geliefert wurde.

Größen der Pakete	n	durch L1 bewiesen	erst durch L2 bewiesen	offen	davon FFD optimal	davon FFD nicht optimal	nicht entschieden
mittel	12	87	0	13	5	8	0
mittel	20	79	0	21	1	19	1
mittel	30	68	0	32	1	21	10
groß	12	38	58	4	4	0	0
groß	20	24	63	13	12	0	1
groß	30	17	65	18	7	1	10
breit	12	49	48	3	3	0	0
breit	20	45	43	12	9	3	0
breit	30	24	63	13	2	2	9

• Mittlere Teile: \(L_2\) beweist in 0 von 300 Instanzen mehr als \(L_1\); das ist kein Zufallsbefund, denn bei Paketen von höchstens halber Kapazität ist \(L_2\) rechnerisch gleich \(L_1\) (siehe oben). Von den entschiedenen offenen Fällen ist FFD bei \(n = 12\) in 8 von 13 nicht optimal, bei \(n = 20\) in 19 von 20 und bei \(n = 30\) in 21 von 22.
• Große Teile: \(L_2\) beweist zusätzlich in 58, 63 und 65 von 100 Instanzen (\(n = 12, 20, 30\)). Von den entschiedenen offenen Fällen ist FFD in 4 von 4, 12 von 12 und 7 von 8 optimal: In diesen Fällen sind die Schranken zu schwach. Bei \(n = 30\) sind 10 von 18 offenen Fällen nicht entschieden.
• Breit gestreute Teile: \(L_2\) beweist zusätzlich in 48, 43 und 63 von 100 Instanzen. Von den entschiedenen offenen Fällen ist FFD in 3 von 3, 9 von 12 und 2 von 4 optimal.
• Nicht entschieden: 31 von 600 Instanzen mit 20 oder 30 Paketen (im Lauf, der die Datei erzeugt hat; die Zahl hängt vom Rechner ab), davon 29 bei \(n = 30\) und 2 bei \(n = 20\). Bei breiten Teilen mit \(n = 30\) sind nur 4 von 13 offenen Fällen entschieden.
• Bewiesen heißt optimal: In den Zellen mit 12 Paketen ist FFD in allen als bewiesen eingeordneten Instanzen gleich dem per DP berechneten Optimum.

Rechnung dieser Seite (Anteil bewiesener Instanzen): Zählt man „durch L1“ und „erst durch L2“ bewiesen zusammen, ergibt sich je Bereich für \(n = 12, 20, 30\): mittel 87, 79, 68; groß 96, 87, 82; breit 97, 88, 87 von je 100. Diese Summen brauchen kein Optimum und sind deshalb von den nicht entschiedenen Instanzen nicht berührt. Der Anteil bewiesener Instanzen sinkt in allen drei Bereichen mit wachsendem \(n\); bei breiten Teilen von 20 auf 30 Pakete nur um 1. Bei 100 Instanzen je Zelle ist dieser Unterschied kein Befund.

Lesart: Bei mittleren Teilen ist \(L_2\) rechnerisch gleich \(L_1\), und unter den entschiedenen offenen Fällen sind bei 20 und 30 Paketen fast alle echte Verluste von FFD (19 von 20, 21 von 22; bei 30 Paketen sind 10 der 32 offenen Fälle nicht entschieden), bei 12 Paketen 8 von 13. Bei großen Teilen sind die Pakete über der halben Kapazität (der Bereich reicht bis 80 %) der Grund, warum \(L_2\) zusätzliche Fälle beweist, und die entschiedenen offenen Fälle sind dort überwiegend solche mit optimalem FFD (4 von 4, 12 von 12, 7 von 8). Bei breit gestreuten Teilen gibt es kein einheitliches Bild (3 von 3, 9 von 12, 2 von 4). Diese Lesart gilt für die entschiedenen offenen Fälle dieser Zellen; bei 12 Paketen ist sie wegen der genannten Instabilität nur eine Richtung, bei 30 Paketen wegen der vielen nicht entschiedenen Instanzen schwach.

Was die Messung zeigt

• Fest: Dass \(L_2 = L_1\) bei Paketen bis zur halben Kapazität gilt, ist eine Rechnung, keine Stichprobe. Ebenso folgt „bewiesen heißt optimal“ aus der Kette der Schranken, solange die Schranken gültig sind; die Demo prüft das bei 12 Paketen nach.
• Tendenz, aber nicht stabil: Die Anteile bei 12 Paketen halten nicht. Mit einem zweiten Satz von 100 Instanzen (Instanznummern 100 bis 199 derselben Zellen) sind bei mittleren Teilen und \(n = 12\) von 13 offenen Fällen 6 (statt 8) nicht optimal, und bei großen Teilen sind von 12 offenen Fällen 10 optimal und 2 nicht optimal (statt 4 und 0 von 4). Gleich blieb nur die Richtung: Bei großen Teilen und \(n = 12\) überwiegen in beiden Sätzen die offenen Fälle mit optimalem FFD. Einzelne Zahlen der Tabelle sind kein Gesetz.
• Schwach: Bei \(n = 30\) bleiben 9 bis 10 von 100 Instanzen je Bereich unentschieden, bei breiten Teilen sind nur 4 von 13 offenen Fällen entschieden. Dort sagt die Messung wenig über die Anteile von „optimal“ und „nicht optimal“, auch weil die Zahl der nicht entschiedenen Instanzen vom Rechner abhängt.
• Nicht gemessen: andere Verfahren als FFD, stärkere Schranken (etwa die LP-Schranke), Paketzahlen über 30, gezielt gebaute Instanzen und Praxisdaten.

Grenzen

• Erfundene Instanzen: gleichverteilte Paketgrößen in drei Bereichen, drei Paketzahlen (12, 20, 30), nur FFD. Praxisdaten kommen nicht vor, über 30 Pakete ist nichts gemessen.
• Wenige Instanzen: 100 Instanzen je Zelle sind wenig, eine einzelne Zelle ist kein Gesetz; bei 12 Paketen sind die Anteile nicht stabil (siehe oben).
• Das Optimum bei 20 und 30 Paketen kommt aus einem ganzzahligen Programm mit Zeitlimit; wie viele Instanzen unentschieden bleiben, hängt von der Rechenzeit ab. Die Datei hält den Stand des Laufs fest.
• Stärkere Schranken als \(L_1\) und \(L_2\) (etwa die LP-Schranke) beweisen mehr Fälle; wie viele, misst die Demo nicht. Mit ihnen ändert sich, welche Fälle offen bleiben.
• Gezielt gebaute Instanzen (etwa solche, in denen genau drei Pakete in einen Container passen) verhalten sich anders; die Demo zeigt sie nicht.
• Form von \(L_2\): Sie ist aus dem Gedächtnis aufgeschrieben und wird gegen die Rechnung über alle ganzzahligen \(\alpha\) und gegen das exakte Optimum getestet, nicht gegen das Original.
• Bedienung: Nach Angabe der README wurde die App im Browser bedient (Desktopbreite; auf Telefonbreite nur das Layout geprüft), nicht auf einem echten Touch-Gerät.

Quellen

• Martello und Toth: die Schranke \(L_2\) geht auf sie zurück (Knapsack Problems, Wiley 1990, Kapitel 8, so im mathematischen Expander der Demo). Die hier benutzte Form ist aus dem Gedächtnis aufgeschrieben, das Original wurde nicht gelesen.
• Die Gütegarantien von FFD in der Literatur nennt die README nur aus Suchtreffern und Sekundärquellen; sie sind hier nicht benutzt.
• Die Demo zum Sortieren und Einsetzen: Sortieren und Einsetzen zeigt nach ihrer README an zwei Beispielmengen und im Mittel über Zufallsinstanzen, dass die Reihenfolge der Pakete die Containerzahl stärker verändert als die Wahl zwischen First Fit und Best Fit, und misst, wie oft FFD die Schranken trifft. Die Demo auf dieser Seite fragt, was ein Verfehlen bedeutet.

Die Literaturangaben stammen aus der README und der App der Demo und sind nicht nachgelesen. Die Zahlen sind eigene Messungen an eigenen, erfundenen Zufallsinstanzen mit festen Startzahlen.