0/1 배낭 문제

용량 제약 아래 가치를 최대화하도록 항목을 고르기.

다른 이름: Knapsack Problem · 0/1 Knapsack · 배낭 문제

정의

각 항목이 무게 $w_i$ 와 가치 $v_i$ 를 가질 때, $\sum w_i x_i \le C$ 를 지키며 $\sum v_i x_i$ 를 최대화하도록 $x_i \in \{0,1\}$ 를 선택한다.

예시

용량 $C = 10$ 인 배낭과 네 개의 항목이 있다고 하자.

항목	무게 $w_i$	가치 $v_i$
1	5	10
2	4	7
3	6	9
4	3	4

무게 합이 10을 넘지 않는 부분집합 중 가치 합이 가장 큰 것은 항목 $\{1, 2\}$ 로, 무게 $5 + 4 = 9 \le 10$ , 가치 $10 + 7 = 17$ 이다. 흥미롭게도 항목 $\{2, 3\}$ 은 무게 $4 + 6 = 10$ 으로 용량을 꽉 채우지만 가치는 $16$ 에 그친다 — 용량을 더 채운다고 해가 더 좋아지는 것은 아니다.

왜 여기 있나

배낭 문제는 절단·적재와 두 가지로 얽힌다: (1) 동적 계획법이라는 공통 방법, (2) 1D 절단 재고의 열 생성에서 가격 산정 부분문제가 곧 배낭 문제다.

주장 & 증거

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

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

이 항목에서 나가는 관계 6

사용 방법
0/1 배낭 문제에서 동적 계획법 (Dynamic Programming)로
0/1 배낭 문제는 의사다항(pseudo-polynomial) 동적 계획법으로 정확히 풀 수 있다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
직접 벤치마크
0/1 배낭 문제에서 OR-Library로
OR-Library는 배낭 계열을 포함한 표준 테스트 인스턴스를 배포한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: B — 서베이 / 튜토리얼 / 커뮤니티OR-Library
  서지정보
  Beasley, J.E. (1990). OR-Library: distributing test problems by electronic mail. JORS 41(11):1069-1072. Hosts instances for knapsack, bin packing, cutting stock and more.
방법 공유
0/1 배낭 문제에서 1D 절단 재고로
절단 재고의 열 생성에서 가격 산정 부분문제가 (정수) 배낭 문제로 나타나, 두 문제는 방법론적으로 맞물린다.
증거A · 동료심사 논문 / 공식 문서
등가E3 · 구조적 유추
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem
  서지정보
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
사용 방법
0/1 배낭 문제에서 분기 한정 (Branch and Bound)로
0/1 배낭 문제는 동적 계획법 외에 분기 한정으로도 정확히 풀 수 있다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법
0/1 배낭 문제에서 정수 선형 계획법 (Integer Linear Programming)로
0/1 배낭 문제는 이진 변수와 단일 용량 제약을 갖는 0/1 정수 선형 계획으로 직접 정식화된다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
오픈소스 구현
0/1 배낭 문제에서 Google OR-Tools로
Google OR-Tools는 0/1 배낭을 푸는 KnapsackSolver를 오픈소스로 제공한다.
증거C · 벤더 / 사례 보고
출처
- 출처 등급: C — 벤더 / 사례 보고Google OR-Tools (새 탭에서 열림)

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
사용 방법 0/1 배낭 문제에서 동적 계획법 (Dynamic Programming)로	0/1 배낭 문제는 의사다항(pseudo-polynomial) 동적 계획법으로 정확히 풀 수 있다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
직접 벤치마크 0/1 배낭 문제에서 OR-Library로	OR-Library는 배낭 계열을 포함한 표준 테스트 인스턴스를 배포한다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: B — 서베이 / 튜토리얼 / 커뮤니티OR-Library 서지정보 Beasley, J.E. (1990). OR-Library: distributing test problems by electronic mail. JORS 41(11):1069-1072. Hosts instances for knapsack, bin packing, cutting stock and more.
방법 공유 0/1 배낭 문제에서 1D 절단 재고로	절단 재고의 열 생성에서 가격 산정 부분문제가 (정수) 배낭 문제로 나타나, 두 문제는 방법론적으로 맞물린다.	A · 동료심사 논문 / 공식 문서	E3 · 구조적 유추	출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem 서지정보 Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
사용 방법 0/1 배낭 문제에서 분기 한정 (Branch and Bound)로	0/1 배낭 문제는 동적 계획법 외에 분기 한정으로도 정확히 풀 수 있다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법 0/1 배낭 문제에서 정수 선형 계획법 (Integer Linear Programming)로	0/1 배낭 문제는 이진 변수와 단일 용량 제약을 갖는 0/1 정수 선형 계획으로 직접 정식화된다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
오픈소스 구현 0/1 배낭 문제에서 Google OR-Tools로	Google OR-Tools는 0/1 배낭을 푸는 KnapsackSolver를 오픈소스로 제공한다.	C · 벤더 / 사례 보고	—	출처 등급: C — 벤더 / 사례 보고Google OR-Tools (새 탭에서 열림)

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

일반화
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 배낭 (직사각형)에서 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.