알고리즘AlgorithmDynamic ProgrammingKnapsackOptimization
냅색 (Knapsack)
한정된 용량의 배낭에 담을 수 있는 물건들의 최대 가치 결정
시각화 로드 중...
알고리즘 복잡도
최선O(N * W)
평균O(N * W)
최악O(N * W)
공간O(N * W)
개요
Algorithm Overview
배낭 문제(0/1 Knapsack Problem)는 한정된 배낭의 최대 적재 무게 한도 내에서 가치의 합이 최대가 되도록 아이템을 선택하는 대표적인 조합 최적화 문제입니다. 물건을 쪼갤 수 없으므로 그리디 접근이 불가능하며 동적 계획법(Dynamic Programming)의 바텀업 타뷸레이션(Tabulation)으로 해결합니다.
01
0/1 냅색의 핵심 점화식 원리
각 아이템 $i$와 현재 배낭의 임시 수용 무게 $w$에 대해 두 가지 선택지를 비교합니다.
- 아이템을 제외하는 경우 (Exclusion): 현재 아이템 무게가 한도를 초과하여 담을 수 없으면 이전 단계의 최적해를 그대로 승계합니다 (
dp[i-1][w]). - 아이템을 포함하는 경우 (Inclusion): 아이템을 담고 남은 잔여 무게(
w - weight[i])에 대한 이전 최적 가치에 현재 아이템의 가치를 합산합니다 (value[i] + dp[i-1][w - weight[i]]). - 최종 점화식:
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])
02
알고리즘 실행 4단계 흐름
- DP 테이블 초기화: 아이템 개수 $N$과 배낭 최대 용량 $W$를 축으로 하는 $(N+1) imes (W+1)$ 2차원 배열을 생성하고 0으로 초기화합니다.
- 행별 순차 순회: 각 아이템을 1번부터 $N$번까지 순회하며, 배낭 무게 한도를 1부터 $W$까지 1씩 증가시키며 최댓값을 계산합니다.
- 테이블 채우기 (Tabulation): 이전 행(상단 셀)과 대각선 좌측 셀(잔여 용량 최적해)을 참조하여 현재 셀의 최적 가치를 결정합니다.
- 역추적 (Backtracking): 테이블의 우측 하단 끝 셀(
dp[N][W])에서부터 거꾸로 추적하여 최종 선택된 아이템 목록을 식별합니다.
실행 예제로 확인하기
용량 5인 0/1 배낭에 A(무게 2, 가치 3), B(무게 3, 가치 4), C(무게 4, 가치 5)가 있다면 A+B는 무게 5에 가치 7입니다. C만 선택하면 가치 5, B만 선택하면 가치 4이므로 최적 선택은 A+B입니다. 각 물건은 한 번만 사용할 수 있습니다.
학습 목표
- 포함·제외 선택지로 DP 테이블을 채우는 이유를 설명할 수 있다.
자주 하는 오해
- 0/1 배낭에서 같은 물건을 여러 번 선택하는 것은 허용되지 않습니다. 탐욕적 가치/무게 비율 정렬도 일반적으로 최적해를 보장하지 않습니다.
핵심 정리
- 정수 무게 한도 W 기준 DP는 O(NW)의 의사다항 시간 복잡도를 갖습니다.
학습 확인
핵심 단계
- 1
아이템과 배낭 무게 한도를 축으로 하는 2차원 DP 테이블을 0으로 초기화
- 2
각 아이템을 차례로 순회하며 배낭 무게 한도에 따른 최대 가치 계산
- 3
현재 아이템을 담지 않는 경우(이전 단계 최적해)와 담는 경우(현재 가치 + 남은 무게 최적해) 중 최댓값 선택
- 4
DP 테이블의 오른쪽 하단 끝 셀에서 최종 최대 가치를 확인하고, 역추적(Backtracking)을 통해 선택된 아이템 식별
핵심 개념 및 실무 적용 분야
✓가치 대비 무게 제한이 있는 예산 배분 및 투자 포트폴리오 최적화
✓화물선, 차량 또는 서버 컨테이너의 제한된 용량 적재 최적화
✓게임 내 인벤토리 한정 무게 대비 최대 가치 아이템 획득 전략
참고 자료
개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.