형식 문제
0/1 배낭 문제
용량 제약 아래 가치를 최대화하도록 항목을 고르기.
다른 이름: Knapsack Problem · 0/1 Knapsack · 배낭 문제
마지막 검증: 2026-05-22
정의
각 항목이 무게 $w_i$와 가치 $v_i$를 가질 때, $\sum w_i x_i \le C$를 지키며 $\sum v_i x_i$를 최대화하도록 $x_i \in {0,1}$를 선택한다.
왜 여기 있나
배낭 문제는 절단·적재와 두 가지로 얽힌다: (1) 동적 계획법이라는 공통 방법, (2) 1D 절단 재고의 열 생성에서 가격 산정 부분문제가 곧 배낭 문제다.
관련 노드
아래 깊이 1 그래프를 참고하라.
주장 & 증거
모든 관계는 등가 수준과 증거 등급을 가진 하나의 주장입니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 사용 방법동적 계획법 (Dynamic Programming) | 0/1 배낭 문제는 의사다항(pseudo-polynomial) 동적 계획법으로 정확히 풀 수 있다. | E0 | A |
|
| 직접 벤치마크OR-Library | OR-Library는 배낭 계열을 포함한 표준 테스트 인스턴스를 배포한다. | E1 | B |
|
| 방법 공유1D 절단 재고 | 절단 재고의 열 생성에서 가격 산정 부분문제가 (정수) 배낭 문제로 나타나, 두 문제는 방법론적으로 맞물린다. | E3 | A |
|
이웃 그래프
직접 연결된 그래프 이웃입니다. 깊이를 전환해 확장하세요.
노드를 클릭하면 열리고 · 엣지를 클릭하면 주장이 보입니다
그래프 불러오는 중…