Metraipolis › archive › dc_30de25dc17bf

Behälterproblem — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-01T02:14:54.695Z
SHA-256 of the archived text
68db630aaeca2490dfa9b5494678c31f0e4ab2801a2511f7d9d9043d0605e4cf
Stable URL of this page
https://metraipolis.com/documento/dc_30de25dc17bf

How to cite

Behälterproblem — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_30de25dc17bf (Metraipolis archive dc_30de25dc17bf, sha256 68db630aaeca2490dfa9b5494678c31f0e4ab2801a2511f7d9d9043d0605e4cf)
BibTeX
@misc{dc30de25dc17bf,
  title = {Behälterproblem — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_30de25dc17bf; sha256 68db630aaeca2490dfa9b5494678c31f0e4ab2801a2511f7d9d9043d0605e4cf},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Das Behälterproblem oder auch bin packing problem ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl k ∈ N {\displaystyle k\in \mathbb {N} } von „Behältern“ (englisch bin) der Größe b ∈ N {\displaystyle b\in \mathbb {N} } und eine Anzahl n ∈ N {\displaystyle n\in \mathbb {N} } „Objekte“ mit den Größen a 1 , a 2 , … , a n ≤ b {\displaystyle a_{1},a_{2},\dotsc ,a_{n}\ \leq \ b} . Frage: Können die n {\displaystyle n} „Objekte“ so auf die k {\displaystyle k} „Behälter“ verteilt (packing) werden, dass keiner der „Behälter“ überläuft? Formal: ∃ f : { 1 , … , n } → { 1 , … , k } , so dass für alle j ∈ { 1 , … , k } ∑ f ( i ) = j a i ≤ b gilt? {\displaystyle \exists \ f\colon \{1,\dotsc ,n\}\to \{1,\dotsc ,k\}{\text{, so dass für alle }}j\in \{1,\dotsc ,k\}\quad \sum _{f(i)=j}a_{i}\leq b{\text{ 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. Man unterscheidet zwischen Offline- und Online-Varianten, wobei offline bedeutet, dass im Voraus alle Objekte bekannt sind. Bei Online-Verfahren muss sofort entschieden werden, in welchen Behälter das Objekt gepackt wird, ohne die folgenden Objekte zu kennen.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Behälterproblem» — https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem
Wikidata Q814581: «operations research problem of packing items into the fewest bins» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q814581
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 256712411, consultata il 2026-11-01T02:06:51.071Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e0e5d411fb875eaab38a300df4c70f81289158e02f4dafefb17f9a5d615239ec