n개 물건의 무게와 가치가 주어졌을 때, 용량이 W인 배낭에 어떤 물건들을 담아야 최대 가치를 얻을 수 있는지, 그리고 실제로 배낭에 포함된 물건들을 출력하는 방법을 살펴봅니다.
0/1 배낭(0/1 Knapsack) 문제란?
배낭(knapsack)은 크기가 정해져 있거나 일정 무게까지만 견딜 수 있는 가방에 비유할 수 있습니다. 배낭에 담으려는 각 물건은 나름의 가치(이익)와 무게를 가지고 있습니다. 우리의 목표는 배낭이 감당할 수 있는 총 무게 범위 안에서 이익이 최대가 되도록 물건을 선택하는 것입니다.
각 물건의 무게와 가치(이익), 그리고 배낭이 수용 가능한 총 무게가 주어졌을 때, 0/1 배낭 문제는 물건의 포함 여부를 0과 1로 표현합니다. 여기서 0은 배낭에 담을 수 없는 물건, 1은 배낭에 포함되는 물건을 의미합니다.
간단한 예제로 이해하기
val[] = {1, 2, 5, 6} // 가치(이익)
wt[] = {2, 3, 4, 5} // 무게
W = 8 // 배낭 용량
이 데이터로 만든 배낭 테이블은 다음과 같은 점화식으로 채울 수 있습니다.
K[i, w] = max{K[i−1, w], K[i−1, w − wt[i]] + Val[i]}
동적 계획법으로 완성된 테이블을 역추적(backtracking)하면 어떤 물건이 선택되었는지 알 수 있습니다.
- K[n][W]에서 역추적을 시작합니다. 이 예제에서 K[n][W] 값은 8입니다.
- 테이블을 위쪽 방향으로 따라 올라가 보면, 값 8은 4번째 행에서 처음 등장합니다. 즉, 4번째 물건을 포함했을 때 최대 이익이 만들어진 것입니다.
- 총 이익 8에서 4번째 물건의 이익 6을 빼면 2가 남습니다.
- 테이블을 다시 역추적해 최대 이익이 2가 되는 지점을 찾으면, 2번째 물건을 추가했을 때임을 알 수 있습니다.
- 결국 2번째 물건과 4번째 물건을 배낭에 담으면 가방을 효율적으로 채우면서 최대 이익을 얻을 수 있습니다.
입력·출력 예시
입력: val[] = {60, 100, 120}
wt[] = {10, 20, 30}
w = 50
출력: 220 // 최대 가치
30 20 // 포함된 무게
설명: 최대 무게 50을 채우기 위해 가치 120인 무게 30과 가치 100인 무게 20을 함께 담습니다.
입력: val[] = {10, 40, 50}
wt[] = {2, 4, 5}
w = 6
출력: 50
4 2
설명: 최대 무게 6을 채우기 위해 가치 40인 무게 4와 가치 10인 무게 2를 함께 담습니다.
알고리즘
시작
단계 1 → 함수 max(int a, int b)
(a > b) ? a : b 반환
단계 2 → 함수 printknapSack(int W, int wt[], int val[], int n)
i, w와 2차원 배열 K[n + 1][W + 1] 선언
i = 0부터 n까지 반복
w = 0부터 W까지 반복
i == 0 또는 w == 0이면
K[i][w] = 0
wt[i - 1] <= w이면
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
그 외의 경우
K[i][w] = K[i - 1][w]
res = K[n][W] 저장 후 res 출력
w = W로 초기화
i = n부터 i > 0 && res > 0인 동안 i-- 하며 반복
res == K[i - 1][w]이면 continue
아니면
wt[i - 1] 출력
res = res - val[i - 1]
w = w - wt[i - 1]
단계 3 → 함수 int main()
val[] = { 50, 120, 70 }
wt[] = { 10, 20, 30 }
W = 50
n = sizeof(val) / sizeof(val[0])
printknapSack(W, wt, val, n) 호출
종료
C++ 코드 구현
#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
// 용량이 W인 배낭에 담긴 물건들을 출력하는 함수
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// bottom-up 방식으로 테이블 K[][]를 채운다
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] +
K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
// 배낭 문제의 최종 결과(최대 가치) 저장
int res = K[n][W];
printf("최대 가치=%d\n", res);
w = W;
printf("포함된 무게\n");
// 역추적을 통해 배낭에 포함된 물건 찾기
for (i = n; i > 0 && res > 0; i--) {
if (res == K[i - 1][w])
continue;
else {
printf("%d ", wt[i - 1]);
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
// 메인 함수
int main() {
int val[] = { 50, 120, 70 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printknapSack(W, wt, val, n);
return 0;
}
실행 결과
최대 가치=190 포함된 무게 30 20
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n×W)이며, DP 테이블을 저장해야 하므로 공간 복잡도 역시 O(n×W)입니다. 테이블을 완성한 뒤 마지막 셀 K[n][W]에서 출발해 역추적하기만 하면, 최대 가치뿐 아니라 어떤 물건이 배낭에 담겼는지도 손쉽게 확인할 수 있습니다.