형식 문제
2D 배낭 (직사각형)
단일 시트에 직사각형 부분집합을 배치해 가치(또는 면적)를 최대화하기.
다른 이름: 2D Knapsack · Rectangle knapsack · 직사각형 배낭
마지막 검증: 2026-05-22
정의
직사각형 후보 집합에서 일부를 선택해 하나의 고정 크기 시트에 겹치지 않게 배치하고, 담은 부품의 총 가치(흔히 면적)를 최대화한다.
계열
빈 패킹·스트립 패킹과 함께 직교 절단·적재의 핵심 문제다. 단일 시트에 "무엇을 담을지" 고르는 선택 구조 때문에 1차원 0/1 배낭 문제와 이름·구조를 공유한다.
관련 노드
아래 깊이 1 그래프를 참고하라.
주장 & 증거
모든 관계는 등가 수준과 증거 등급을 가진 하나의 주장입니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 사용 방법동적 계획법 (Dynamic Programming) | 2D 배낭 변형은 동적 계획법 및 그 위에 구축된 정확·근사 방법으로 다뤄져 왔다. | E2 | B |
|
| 직접 벤치마크2DPackLib | 2DPackLib은 2차원 직교 배낭(knapsack) 인스턴스를 포함한다. | E1 | A |
|
| 방법 공유2D 빈 패킹 | 2D 배낭과 빈 패킹은 직교 배치 핵심과 다수의 정확·휴리스틱 방법을 공유한다. | E2 | B |
|
| 일반화0/1 배낭 문제 | 2D 배낭은 1차원 0/1 배낭 문제의 2차원 일반화로, 항목 선택 구조를 기하학적 배치로 확장한다. | E2 | B |
|
| 사용 방법분기 한정 (Branch and Bound) | 2D 배낭의 정확 접근은 분기 한정 정식화로 보고되어 왔다. | E2 | B |
|
이웃 그래프
직접 연결된 그래프 이웃입니다. 깊이를 전환해 확장하세요.
노드를 클릭하면 열리고 · 엣지를 클릭하면 주장이 보입니다
그래프 불러오는 중…