Behälterproblem

Bin Packing ist ein Problem der Theoretischen Informatik, 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“
  $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 ?}}$

Bin Packing liegt in NP und gehört zu den NP-vollständigen Problemen.

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: Rucksackproblem, Operations Research, Komplexitätsklasse