2D 배낭 (직사각형)

단일 시트에 직사각형 부분집합을 배치해 가치(또는 면적)를 최대화하기.

다른 이름: 2D Knapsack · Rectangle knapsack · 직사각형 배낭

정의

직사각형 후보 집합에서 일부를 선택해 하나의 고정 크기 시트에 겹치지 않게 배치하고, 담은 부품의 총 가치(흔히 면적)를 최대화한다.

예시

시트 $4\times4$ , 후보가 $3\times3$ (가치 9), $4\times1$ (가치 4), $1\times3$ (가치 3), $2\times2$ (가치 4)라고 하자. 앞의 세 개를 고르면 $3\times3$ 을 왼쪽 아래, $4\times1$ 을 맨 위 행, $1\times3$ 을 오른쪽 열에 놓아 시트를 빈틈없이 채우며 가치 $9+4+3=16$ 을 얻는다. $2\times2$ 까지 담으면 면적이 시트를 넘으므로, 최적은 이 세 개의 선택이다.

계열

빈 패킹·스트립 패킹과 함께 직교 절단·적재의 핵심 문제다. 단일 시트에 "무엇을 담을지" 고르는 선택 구조 때문에 1차원 0/1 배낭 문제와 이름·구조를 공유한다.

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목에서 나가는 관계 6

사용 방법
2D 배낭 (직사각형)에서 동적 계획법 (Dynamic Programming)로
2D 배낭 변형은 동적 계획법 및 그 위에 구축된 정확·근사 방법으로 다뤄져 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
직접 벤치마크
2D 배낭 (직사각형)에서 2DPackLib로
2DPackLib은 2차원 직교 배낭(knapsack) 인스턴스를 포함한다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서2DPackLib: a two-dimensional cutting and packing library
  서지정보
  Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
방법 공유
2D 배낭 (직사각형)에서 2D 빈 패킹로
2D 배낭과 빈 패킹은 직교 배치 핵심과 다수의 정확·휴리스틱 방법을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
일반화
2D 배낭 (직사각형)에서 0/1 배낭 문제로
2D 배낭은 1차원 0/1 배낭 문제의 2차원 일반화로, 항목 선택 구조를 기하학적 배치로 확장한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법
2D 배낭 (직사각형)에서 분기 한정 (Branch and Bound)로
기하학적 2D 배낭의 정확 해법으로 분기 한정 알고리즘이 제시되었으며, 1차원 배낭 완화(직사각형 면적을 무게로)를 경계로 쓴다(Caprara & Monaci 2004).
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서On the two-dimensional Knapsack Problem
  서지정보
  Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
사용 방법
2D 배낭 (직사각형)에서 유전 알고리즘 (Genetic Algorithm)로
2D 배낭 변형은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
사용 방법 2D 배낭 (직사각형)에서 동적 계획법 (Dynamic Programming)로	2D 배낭 변형은 동적 계획법 및 그 위에 구축된 정확·근사 방법으로 다뤄져 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
직접 벤치마크 2D 배낭 (직사각형)에서 2DPackLib로	2DPackLib은 2차원 직교 배낭(knapsack) 인스턴스를 포함한다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서2DPackLib: a two-dimensional cutting and packing library 서지정보 Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
방법 공유 2D 배낭 (직사각형)에서 2D 빈 패킹로	2D 배낭과 빈 패킹은 직교 배치 핵심과 다수의 정확·휴리스틱 방법을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
일반화 2D 배낭 (직사각형)에서 0/1 배낭 문제로	2D 배낭은 1차원 0/1 배낭 문제의 2차원 일반화로, 항목 선택 구조를 기하학적 배치로 확장한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법 2D 배낭 (직사각형)에서 분기 한정 (Branch and Bound)로	기하학적 2D 배낭의 정확 해법으로 분기 한정 알고리즘이 제시되었으며, 1차원 배낭 완화(직사각형 면적을 무게로)를 경계로 쓴다(Caprara & Monaci 2004).	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서On the two-dimensional Knapsack Problem 서지정보 Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
사용 방법 2D 배낭 (직사각형)에서 유전 알고리즘 (Genetic Algorithm)로	2D 배낭 변형은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목으로 들어오는 관계 4

방법 공유
2D 스트립 패킹에서 2D 배낭 (직사각형)로
스트립 패킹과 2D 배낭은 직교 배치 핵심과 방법론을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유
길로틴 절단에서 2D 배낭 (직사각형)로
길로틴 제약 하의 단일 시트 최대화는 길로틴 2D 배낭으로, 2D 배낭과 방법론을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유
팔레트 적재에서 2D 배낭 (직사각형)로
단일 영역에 동일 직사각형을 최대로 채우는 (제조사) 팔레트 적재는 2D 배낭형 배치 방법과 닿아 있다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E3 · 구조적 유추
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
언급
Wäscher 절단·적재 유형론 (Wäscher Typology)에서 2D 배낭 (직사각형)로
유형론은 2D 배낭을 '출력 최대화'(고정 자원에 담는 가치를 최대화) 유형으로 분류한다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
방법 공유 2D 스트립 패킹에서 2D 배낭 (직사각형)로	스트립 패킹과 2D 배낭은 직교 배치 핵심과 방법론을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유 길로틴 절단에서 2D 배낭 (직사각형)로	길로틴 제약 하의 단일 시트 최대화는 길로틴 2D 배낭으로, 2D 배낭과 방법론을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유 팔레트 적재에서 2D 배낭 (직사각형)로	단일 영역에 동일 직사각형을 최대로 채우는 (제조사) 팔레트 적재는 2D 배낭형 배치 방법과 닿아 있다.	B · 서베이 / 튜토리얼 / 커뮤니티	E3 · 구조적 유추	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
언급 Wäscher 절단·적재 유형론 (Wäscher Typology)에서 2D 배낭 (직사각형)로	유형론은 2D 배낭을 '출력 최대화'(고정 자원에 담는 가치를 최대화) 유형으로 분류한다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.