Benutzte Behälter
Untere Schranke
Minimum

      Gewichte der Gegenstände (kg)

        Mehr über das Behälterproblem

        Behälterproblem (Bin Packing)

        Kisten in Transporter, Dateien auf Datenträger, Aufträge auf Maschinen: Das Behälterproblem fragt, wie man eine Liste von Gegenständen in möglichst wenige gleich große Behälter bekommt. Es ist kein schnelles Verfahren bekannt, das immer die beste Packung findet, aber einfache Regeln kommen nahe heran. Wählen Sie eine Regel, gehen Sie sie Schritt für Schritt durch und vergleichen Sie mit der exakten Lösung. Tippen Sie auf einen Gegenstand im Regal und dann auf einen Behälter, um ihn hineinzulegen: Grüne Behälter haben Platz dafür, und Neuer Behälter öffnet einen weiteren. Tippen Sie auf einen Gegenstand in einem Behälter, um ihn wieder herauszunehmen. Packen Sie alle Gegenstände in so wenige Behälter wie möglich; die untere Schranke (das Gesamtgewicht geteilt durch die Behältergröße, aufgerundet) und das Minimum zeigen, wie nah Sie dran sind, und Wenigste Behälter zeigt die beste Packung. Ändern Sie die Gewichte der Gegenstände (in Kilogramm) und die Behältergröße im Bedienfeld. Die Ansicht Schritt für Schritt zeigt, wie die schnellen Regeln packen: Next Fit, First Fit oder Best Fit, mit den Gegenständen in der eingegebenen Reihenfolge oder nach Größe sortiert, der größte zuerst, oder die exakte Lösung, die die dynamische Programmierung findet. Drücken Sie Abspielen, um zuzusehen, wie die Gegenstände in die Behälter kommen, oder Schritt und Zurück, um Schritt für Schritt vorzugehen, und ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Wenn die Spielfläche ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

        Wie es funktioniert

        1. Tippen Sie auf einen Gegenstand und dann auf einen Behälter mit Platz, um ihn hineinzulegen, oder auf Neuer Behälter, um einen weiteren zu öffnen.
        2. Versuchen Sie, so wenige Behälter wie möglich zu verwenden, oder drücken Sie Wenigste Behälter, um die beste Packung zu sehen.
        3. Öffnen Sie die Ansicht Schritt für Schritt, wählen Sie eine Regel und drücken Sie Abspielen, um zu sehen, wie jeder Gegenstand die Behälter ausprobiert.

        Die Regeln

        Next Fit hält nur den letzten Behälter offen: Ein Gegenstand, der dort nicht passt, beginnt einen neuen Behälter. First Fit probiert die Behälter vom ersten an und nimmt den ersten mit genug Platz. Best Fit probiert jeden Behälter und nimmt den vollsten mit genug Platz, sodass am wenigsten Platz ungenutzt bleibt. First Fit und Best Fit können die Gegenstände auch zuerst vom größten zum kleinsten sortieren; das ergibt First Fit Decreasing und Best Fit Decreasing.

        Die exakte Lösung

        Die letzte Regel ist keine Faustregel: Sie findet die wenigsten Behälter durch dynamische Programmierung über die Mengen von Gegenständen. Für jede Menge von Gegenständen merkt sie sich die wenigsten Behälter, die sie aufnehmen, und unter den Packungen mit so vielen Behältern die kleinste Füllung im letzten Behälter. Eine Menge wächst um jeweils einen Gegenstand, der entweder den letzten Behälter auffüllt oder einen neuen öffnet. Bei n Gegenständen gibt es 2ⁿ Mengen, deshalb erlaubt die App höchstens 12 Gegenstände. Die untere Schranke, also die Gesamtgröße geteilt durch die Behältergröße und aufgerundet, zeigt, wie nah eine Packung am Ziel ist.

        Häufig gestellte Fragen

        Welche Regel ist beim Behälterproblem die beste?

        Von den schnellen Regeln sind First Fit Decreasing und Best Fit Decreasing die stärksten: Sie brauchen nie mehr als 11/9 der wenigsten Behälter plus eine kleine Konstante. First Fit und Best Fit mit unsortierten Gegenständen bleiben innerhalb des 1,7-Fachen der wenigsten Behälter, Next Fit innerhalb des 2-Fachen.

        Warum ist das Behälterproblem schwer?

        Schon die Frage, ob die Gegenstände in nur zwei Behälter passen, ist das Partitionsproblem, und das ist NP-vollständig. Solange also nicht P = NP gilt, findet kein Verfahren für jede Eingabe schnell die wenigsten Behälter, und exakte Verfahren brauchen im schlimmsten Fall exponentielle Zeit.

        Was ist die untere Schranke?

        Die Gesamtgröße der Gegenstände geteilt durch die Behältergröße, aufgerundet. Keine Packung kann weniger Behälter benutzen, denn die Behälter müssen alle Gegenstände aufnehmen. Oft erreicht die beste Packung diesen Wert, aber nicht immer: Drei Gegenstände der Größe 6 bei Behältern der Größe 10 haben eine untere Schranke von 2 und brauchen 3 Behälter.

        Ist das dynamische Programmierung?

        Die exakte Lösung ja: Sie baut die beste Packung für jede Menge von Gegenständen aus den besten Packungen kleinerer Mengen auf. Die schnellen Regeln sind Greedy-Verfahren, die einmal entscheiden und nie zurückblicken.

        Wird irgendetwas gesendet?

        Nein. Alles wird in Ihrem Browser berechnet, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

        Bereit, es auszuprobieren?

        Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

        Zum Editor