Bin Packing Problem

Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert:

  • Gegeben: Eine Anzahl
    k \in \mathbb{N}
    von „Behältern“ (englisch bin) der Größe
    b \in \mathbb{N}
    und eine Anzahl
    n \in \mathbb{N}
    „Objekte“ mit den Größen
     a_1,a_2,..,a_n\ \leq\ b
    .
  • Frage: Können die n „Objekte“ so auf die k „Behälter“ verteilt (packing) werden, dass keiner der „Behälter“ überläuft?
Formal:
 \exists\ f : \{1,..,n\} \to \{1,..,k\}\ \mbox{, so dass }\forall\ j := 1,..,k \quad \sum_{f(i)=j} a_i \leq b \mbox{  gilt ?}

Das oben beschriebene Entscheidungsproblem ist NP-vollständig; das zugehörige Optimierungsproblem – das Finden einer Zuordnung bei der die Anzahl an Behältern minimiert wird – ist NP-schwer.

Die hier gegebene Formulierung des Bin-Packing-Problems ist nur die Motivation beziehungsweise Basis für eine Vielzahl weiterer Packing Problems, die unter anderem in der Verpackungsindustrie eine große Rolle spielen.

Eine etwas allgemeiner formale Definition beschreibt das Bin-Packing-Problem als die Bestimmung einer Partition und Zuordnung einer Menge von Objekten, so dass eine bestimmte Bedingung erfüllt bzw. eine Zielfunktion minimiert oder maximiert wird.

Siehe auch

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bin packing problem — In computational complexity theory, the bin packing problem is a combinatorial NP hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.There… …   Wikipedia

  • Bin-Packing-Problem — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin packing problem — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Packing problem — Part of a series on Puzzles …   Wikipedia

  • BIN PACKING — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin-Packing — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin-packing — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Probleme de bin packing — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Problème de bin packing — Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème classique se définit en une …   Wikipédia en Français

  • Knapsack problem — BKP redirects here. For other uses, see BKP (disambiguation). Example of a one dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”