배낭 문제 (Knapsack) 시각화
무게 제한 내 최대 가치 조합을 찾는 대표적인 DP 문제
동적 프로그래밍★★☆
속도
1 / 1최대 가치: -총 무게: -/7선택 아이템: -
프리셋
아이템
⛺
w:3 v:4
🛏️
w:2 v:3
🍖
w:4 v:5
💧
w:1 v:2
🔦
w:1 v:3
각 단계를 클릭하면 해당 시점으로 이동합니다.
실행 버튼을 눌러 시작하세요.
배낭 문제란?
무게 제한이 있는 배낭에 최대 가치의 아이템 조합을 담는 최적화 문제입니다. 0/1 배낭 문제는 각 아이템을 넣거나(1) 빼거나(0) 두 가지 선택만 가능합니다. dp[i][w]는 '처음 i개 아이템으로 용량 w를 채울 때의 최대 가치'를 저장합니다.
사용 방법
- 1프리셋(캠핑/보물/공부)을 선택하거나 용량을 조절합니다
- 2실행 버튼을 눌러 DP 테이블 채우기를 시작합니다
- 3셀 위에 마우스를 올리면 dp[i][w] 값을 확인할 수 있습니다
- 4역추적 단계에서 선택된 아이템이 하이라이트됩니다
- 5단계 탭에서 포함/제외 결정 과정을 확인합니다
동작 원리
- 1dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i): 아이템 i를 넣을 때와 뺄 때의 최대값을 비교합니다
- 2아이템의 무게가 현재 용량보다 크면 넣을 수 없으므로 dp[i][w] = dp[i-1][w]
- 3테이블을 모두 채운 후 dp[n][W]에서 역방향으로 추적하여 선택된 아이템을 찾습니다
- 4시간 복잡도 O(n*W), 공간 복잡도 O(n*W). 의사 다항 시간 알고리즘입니다
실무 활용
- •투자 포트폴리오 최적화 — 예산 내 수익 극대화
- •화물 적재 — 트럭/컨테이너 무게 제한 내 가치 극대화
- •클라우드 자원 배분 — CPU/메모리 제한 내 작업 스케줄링
- •광고 예산 배분 — 예산 내 노출 극대화
학습 팁
- •먼저 캠핑 프리셋으로 작은 예제를 풀어보세요
- •include vs exclude 결정에서 두 값을 비교하는 것이 핵심입니다
- •역추적 단계를 주의 깊게 보면 dp[i][w] != dp[i-1][w]인 행이 선택된 아이템임을 알 수 있습니다
자주 묻는 질문
Q. 0/1 배낭과 분할 배낭의 차이는?
A. 0/1 배낭은 아이템을 쪼갤 수 없고(DP 필요), 분할 배낭(Fractional)은 쪼갤 수 있어 그리디 알고리즘으로 풀 수 있습니다.
Q. 왜 의사 다항 시간인가요?
A. O(n*W)에서 W가 입력 크기(비트 수)가 아닌 값 자체이기 때문입니다. W의 비트 수가 b라면 실제 복잡도는 O(n*2^b)로 지수 시간입니다.