형식 문제
2D 배낭 (직사각형)
단일 시트에 직사각형 부분집합을 배치해 가치(또는 면적)를 최대화하기.
다른 이름: 2D Knapsack · Rectangle knapsack · 직사각형 배낭
마지막 검증: 2026-05-27
정의
직사각형 후보 집합에서 일부를 선택해 하나의 고정 크기 시트에 겹치지 않게 배치하고, 담은 부품의 총 가치(흔히 면적)를 최대화한다.
예시
시트 , 후보가 (가치 9), (가치 4), (가치 3), (가치 4)라고 하자. 앞의 세 개를 고르면 을 왼쪽 아래, 을 맨 위 행, 을 오른쪽 열에 놓아 시트를 빈틈없이 채우며 가치 을 얻는다. 까지 담으면 면적이 시트를 넘으므로, 최적은 이 세 개의 선택이다.
계열
빈 패킹·스트립 패킹과 함께 직교 절단·적재의 핵심 문제다. 단일 시트에 "무엇을 담을지" 고르는 선택 구조 때문에 1차원 0/1 배낭 문제와 이름·구조를 공유한다.
관련 노드
아래 깊이 1 그래프를 참고하라.
주장 & 증거
모든 관계는 등가 수준과 증거 등급을 가진 하나의 주장입니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 사용 방법동적 계획법 (Dynamic Programming) | 2D 배낭 변형은 동적 계획법 및 그 위에 구축된 정확·근사 방법으로 다뤄져 왔다. | — | B |
|
| 직접 벤치마크2DPackLib | 2DPackLib은 2차원 직교 배낭(knapsack) 인스턴스를 포함한다. | — | A |
|
| 방법 공유2D 빈 패킹 | 2D 배낭과 빈 패킹은 직교 배치 핵심과 다수의 정확·휴리스틱 방법을 공유한다. | E2 | B |
|
| 일반화0/1 배낭 문제 | 2D 배낭은 1차원 0/1 배낭 문제의 2차원 일반화로, 항목 선택 구조를 기하학적 배치로 확장한다. | E2 | B |
|
| 사용 방법분기 한정 (Branch and Bound) | 기하학적 2D 배낭의 정확 해법으로 분기 한정 알고리즘이 제시되었으며, 1차원 배낭 완화(직사각형 면적을 무게로)를 경계로 쓴다(Caprara & Monaci 2004). | — | A |
|
| 사용 방법유전 알고리즘 (Genetic Algorithm) | 2D 배낭 변형은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다. | — | B |
|
이웃 그래프
직접 연결된 그래프 이웃입니다. 깊이를 전환해 확장하세요.
노드를 클릭하면 열리고 · 엣지를 클릭하면 주장이 보입니다
함께 보기
직접 연결되어 있지 않지만, 공유하는 연결과 설명으로 보아 개념적으로 가까운 노드입니다.