C언어로 배우는 0-1 배낭 문제(0-1 Knapsack Problem): 개념부터 코드까지

배낭(Knapsack)은 짐을 담는 가방을 뜻합니다. 배낭 문제는 각 물건의 가치를 기준으로 가방에 어떤 물건을 넣을지 결정하는 문제로, 그 목표는 가방에 담긴 물건들의 총 가치를 최대화하는 것입니다. 특히 0-1 배낭 문제(0-1 Knapsack Problem)에서는 물건을 통째로 넣거나 아예 버리는 두 가지 선택지만 가능하며, 물건의 일부만 잘라서 넣는 것은 허용되지 않습니다.

예시 문제

물건들의 가치 = {20, 25, 40}
물건들의 무게 = {25, 20, 30}
가방의 수용 가능한 무게(용량) = 50

무게 조합 분석

가방 용량이 50이므로, 물건들을 조합했을 때 총 무게가 50을 넘지 않아야 합니다.

{1, 2} 조합 : 무게 = 25 + 20 = 45, 가치 = 20 + 25 = 45
{2, 3} 조합 : 무게 = 20 + 30 = 50, 가치 = 25 + 40 = 65

{1, 3} 조합은 무게가 55로 최대 허용 무게인 50을 초과하기 때문에 사용할 수 없습니다.
두 조합을 비교해 보면 {2, 3} 조합의 가치가 65로 더 크므로, 2번과 3번 물건을 배낭에 넣는 것이 최적해입니다.

C언어로 구현하는 0-1 배낭 문제 프로그램

아래 코드는 동적 계획법(Dynamic Programming)을 활용한 대표적인 풀이 방식입니다. 2차원 배열 knap[i][w]에는 "i번째 물건까지 고려했을 때, 무게 w 이하로 담을 수 있는 최대 가치"가 저장됩니다. 각 단계마다 현재 물건을 배낭에 넣는 경우와 넣지 않는 경우 중 더 큰 가치를 선택하며 표를 채워 나가고, 최종적으로 knap[n][W]에 전체 문제의 최적해가 남습니다.

#include<stdio.h>
int max(int a, int b) {
    if(a>b){
        return a;
    } else {
        return b;
    }
}
int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int knap[n+1][W+1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i==0 || w==0)
                knap[i][w] = 0;
            else if (wt[i-1] <= w)
                knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
            else
                knap[i][w] = knap[i-1][w];
        }
    }
    return knap[n][W];
}
int main() {
    int val[] = {20, 25, 40};
    int wt[] = {25, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("The solution is : %d", knapsack(W, wt, val, n));
    return 0;
}

실행 결과

The solution is : 65

프로그램을 실행하면 앞서 손으로 계산한 결과와 동일하게 최대 가치 65가 출력되는 것을 확인할 수 있습니다. 이처럼 동적 계획법을 활용하면 모든 조합을 일일이 검사하는 완전 탐색보다 훨씬 효율적으로 0-1 배낭 문제를 해결할 수 있습니다.