Formal problem
2D 빈 패킹
직사각형을 최소 개수의 고정 크기 빈에 채우기.
Also called: 2D Bin Packing · 이차원 빈 패킹 · 2BP · 직사각형 빈 패킹
Last verified: 2026-05-22
정의
축 정렬 직사각형을 겹치지 않게 동일한 고정 크기 빈에 채워, 사용 빈 개수를 최소화한다.
계열
2D 스트립 패킹, 2D 배낭과 함께 Wäscher 외 분류 체계의 핵심 직교 절단·적재 문제 중 하나다. 기하(직사각형 한정)에서 불규칙 네스팅과 대비되지만, 해법 방법론의 일부는 공유한다.
벤치마크
2DPackLib이 직접 벤치마크다(등급 A).
관련 노드
아래 깊이 1 그래프를 참고하라.
Claims & evidence
Every relationship is a claim with an equivalence level and an evidence grade. See the evidence policy.
| Relationship | Claim | Equiv. | Evidence | Sources |
|---|---|---|---|---|
| shares method with2D 스트립 패킹 | 2D 빈 패킹과 스트립 패킹은 구성적·정확 방법을 공유하며, 단일 빈을 채울 때 스트립 패킹이 부분문제로 자주 등장한다. | E2 | B |
|
| direct benchmark2DPackLib | 2DPackLib은 2차원 직교 빈 패킹의 표준 인스턴스를 제공한다. | E1 | A |
|
| uses method분기 한정 (Branch and Bound) | 2D 빈 패킹의 정확 접근은 분기 한정(및 분기-가격) 정식화로 보고되어 왔다. | E2 | B |
|
| uses method감소 우선 적합 (First-Fit Decreasing) | 감소 우선 적합(FFD) 계열의 구성적 휴리스틱이 빈 패킹의 빠른 근사해에 널리 쓰인다. | E2 | B |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
Click a node to open it · click an edge for its claim
Loading graph…