Formal problem
0/1 배낭 문제
용량 제약 아래 가치를 최대화하도록 항목을 고르기.
Also called: Knapsack Problem · 0/1 Knapsack · 배낭 문제
Last verified: 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 그래프를 참고하라.
Claims & evidence
Every relationship is a claim with an equivalence level and an evidence grade. See the evidence policy.
| Relationship | Claim | Equiv. | Evidence | Sources |
|---|---|---|---|---|
| uses method동적 계획법 (Dynamic Programming) | 0/1 배낭 문제는 의사다항(pseudo-polynomial) 동적 계획법으로 정확히 풀 수 있다. | E0 | A |
|
| direct benchmarkOR-Library | OR-Library는 배낭 계열을 포함한 표준 테스트 인스턴스를 배포한다. | E1 | B |
|
| shares method with1D 절단 재고 | 절단 재고의 열 생성에서 가격 산정 부분문제가 (정수) 배낭 문제로 나타나, 두 문제는 방법론적으로 맞물린다. | E3 | A |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
Click a node to open it · click an edge for its claim
Loading graph…