C++로 0-1 배낭 문제(0-1 Knapsack Problem) 해결하기 – 재귀 알고리즘과 예제 코드

0-1 배낭 문제(0-1 Knapsack Problem)는 각각 고유한 무게와 가치를 가진 물건들이 주어졌을 때, 전체 무게가 주어진 한도를 초과하지 않으면서 전체 가치가 최대가 되도록 배낭에 담을 물건을 선택하는 대표적인 최적화 문제입니다. 문제 이름 그대로 각 물건은 배낭에 '넣는다(1)' 또는 '넣지 않는다(0)'의 두 가지 선택지만 가능하며, 물건을 잘라 부분적으로 담을 수 없다는 점이 특징입니다.

입력

Value = [10, 20, 30, 40, 60, 70]
Weight = [1, 2, 3, 6, 7, 4]
int W = 7

출력

knapsack value is: 100

알고리즘

시작
   입력: 각각 무게와 가치를 가진 물건들의 집합
   배낭 용량(W) 설정
   물건의 개수 n = sizeof(values) / sizeof(values[0])
   knapSack(가치 배열 v, 무게 배열 w, 물건 개수 n, 배낭 용량 W) 호출
   만약 (W < 0)이면
      반환
   남은 물건이 없거나 용량이 0이 되면
      0 반환
   현재 물건 n을 배낭에 포함한 뒤(v[n]),
   남은 물건(n - 1)에 대해 줄어든 용량(W - w[n])으로 재귀 호출
   현재 물건 n을 배낭에서 제외한 뒤,
   남은 물건(n - 1)에 대해 재귀 호출
   포함한 경우와 제외한 경우 중 더 큰 가치를 반환
끝

예제 코드

#include <iostream>
#include <climits>
using namespace std;
int knapSack(int v[], int w[], int n, int W) {
    if (W < 0)
        return INT_MIN;
    if (n < 0 || W == 0)
        return 0;
    int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
    int ex = knapSack(v, w, n - 1, W);
    return max(in, ex);
}
int main() {
    int v[] = { 10, 20, 30, 40, 60, 70 };
    int w[] = { 1, 2, 3, 6, 7, 4 };
    int W = 7;
    int n = sizeof(v) / sizeof(v[0]);
    cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
    return 0;
}

출력 결과

Knapsack value is 100

코드 설명

knapSack 함수는 재귀 방식으로 동작합니다. 먼저 용량 W가 음수가 되면 유효하지 않은 상태이므로 INT_MIN을 반환하여 해당 경로가 선택되지 않도록 처리합니다. 남은 물건이 없거나(n < 0) 배낭 용량이 0이면 더 이상 가치를 추가할 수 없으므로 0을 반환합니다.

그 다음 두 가지 경우를 모두 탐색합니다. 첫 번째는 현재 물건을 배낭에 포함하는 경우로, 물건의 가치 v[n]을 더하고 용량을 w[n]만큼 줄인 상태로 나머지 물건들을 재귀적으로 처리합니다. 두 번째는 현재 물건을 제외하는 경우로, 용량을 그대로 유지한 채 나머지 물건들을 처리합니다. 마지막으로 두 경우 중 더 큰 값을 max()로 선택하여 반환함으로써 최적의 배낭 가치를 구할 수 있습니다.

위 예제에서는 용량 7인 배낭에 가치 [10, 20, 30, 40, 60, 70], 무게 [1, 2, 3, 6, 7, 4]인 물건들을 넣었을 때, 최적 조합으로 배낭 가치 100을 얻습니다. 이러한 순수 재귀 방식은 시간 복잡도가 O(2ⁿ)으로 물건 수가 많아지면 비효율적일 수 있으며, 실무에서는 메모이제이션이나 동적 계획법(DP)을 함께 활용하면 성능을 크게 개선할 수 있습니다.