Formal problem
2D 배낭 (직사각형)
단일 시트에 직사각형 부분집합을 배치해 가치(또는 면적)를 최대화하기.
Also called: 2D Knapsack · Rectangle knapsack · 직사각형 배낭
Last verified: 2026-05-22
정의
직사각형 후보 집합에서 일부를 선택해 하나의 고정 크기 시트에 겹치지 않게 배치하고, 담은 부품의 총 가치(흔히 면적)를 최대화한다.
계열
빈 패킹·스트립 패킹과 함께 직교 절단·적재의 핵심 문제다. 단일 시트에 "무엇을 담을지" 고르는 선택 구조 때문에 1차원 0/1 배낭 문제와 이름·구조를 공유한다.
관련 노드
아래 깊이 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 |
|---|---|---|---|---|
| uses method동적 계획법 (Dynamic Programming) | 2D 배낭 변형은 동적 계획법 및 그 위에 구축된 정확·근사 방법으로 다뤄져 왔다. | E2 | B |
|
| direct benchmark2DPackLib | 2DPackLib은 2차원 직교 배낭(knapsack) 인스턴스를 포함한다. | E1 | A |
|
| shares method with2D 빈 패킹 | 2D 배낭과 빈 패킹은 직교 배치 핵심과 다수의 정확·휴리스틱 방법을 공유한다. | E2 | B |
|
| generalizes0/1 배낭 문제 | 2D 배낭은 1차원 0/1 배낭 문제의 2차원 일반화로, 항목 선택 구조를 기하학적 배치로 확장한다. | E2 | B |
|
| uses method분기 한정 (Branch and Bound) | 2D 배낭의 정확 접근은 분기 한정 정식화로 보고되어 왔다. | E2 | B |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
Click a node to open it · click an edge for its claim
Loading graph…