이 글에서는 동적 계획법(Dynamic Programming)을 활용해 0-1 배낭 문제(0-1 Knapsack Problem)를 해결하는 C++ 프로그램을 소개합니다. 0-1 배낭 문제란 각각 고유한 무게와 가치를 가진 여러 아이템이 주어졌을 때, 배낭의 용량 한도를 초과하지 않으면서 담을 수 있는 아이템들의 총 가치를 최대화하는 조합을 찾는 문제입니다. 각 아이템은 배낭에 넣거나(1) 넣지 않거나(0) 둘 중 하나만 선택할 수 있기 때문에 '0-1'이라는 이름이 붙었습니다.
알고리즘
시작
무게와 가치를 가진 아이템 집합을 입력받는다
배낭의 용량을 설정한다
두 정수 중 더 큰 값을 반환하는 함수를 만든다
용량 W인 배낭에 담을 수 있는 최대 가치를 반환하는 함수를 만든다
int knapSack(int W, int w[], int v[], int n)
int i, wt;
int K[n + 1][W + 1]
for i = 0 to n
for wt = 0 to W
if (i == 0 or wt == 0)
K[i][wt] = 0
else if (w[i - 1] <= wt)
K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt])
else
K[i][wt] = K[i - 1][wt]
return K[n][W]
함수를 호출하고 결과를 출력한다
끝동적 계획법의 핵심 원리
이 알고리즘은 2차원 테이블 K[n+1][W+1]을 사용합니다. K[i][wt]에는 '첫 i개의 아이템만 고려하고 배낭 용량이 wt일 때 얻을 수 있는 최대 가치'가 저장됩니다. 점화식은 다음과 같이 구성됩니다.
- 현재 아이템의 무게가 남은 용량보다 클 경우: 해당 아이템을 담을 수 없으므로
K[i][wt] = K[i-1][wt] - 담을 수 있을 경우: 아이템을 넣었을 때와 넣지 않았을 때의 가치를 비교해 더 큰 값 선택 →
K[i][wt] = max(v[i-1] + K[i-1][wt-w[i-1]], K[i-1][wt])
시간 복잡도와 공간 복잡도는 모두 O(n × W)로, 완전 탐색의 지수 시간 복잡도보다 훨씬 효율적입니다.
예제 코드
#include <iostream>
using namespace std;
int max(int x, int y) {
return (x > y) ? x : y;
}
int knapSack(int W, int w[], int v[], int n) {
int i, wt;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (wt = 0; wt <= W; wt++) {
if (i == 0 || wt == 0)
K[i][wt] = 0;
else if (w[i - 1] <= wt)
K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
else
K[i][wt] = K[i - 1][wt];
}
}
return K[n][W];
}
int main() {
cout << "배낭에 넣을 아이템 개수 입력:";
int n, W;
cin >> n;
int v[n], w[n];
for (int i = 0; i < n; i++) {
cout << "아이템 " << i << "의 가치와 무게 입력:";
cin >> v[i];
cin >> w[i];
}
cout << "배낭의 용량 입력:";
cin >> W;
cout << knapSack(W, w, v, n);
return 0;
}실행 결과
배낭에 넣을 아이템 개수 입력:4 아이템 0의 가치와 무게 입력:10 50 아이템 1의 가치와 무게 입력:20 60 아이템 2의 가치와 무게 입력:30 70 아이템 3의 가치와 무게 입력:40 90 배낭의 용량 입력:100 40
위 실행 결과에서 배낭 용량이 100일 때, 무게 50·가치 10, 무게 60·가치 20인 아이템을 함께 담으면 총 무게가 110으로 한도를 초과합니다. 따라서 무게 90에 가치 40인 아이템 하나를 담는 것이 최적해가 되며, 프로그램은 최대 가치 40을 올바르게 출력합니다.