[백준/C언어] 12865번 - 평범한 배낭

백준 웹사이트 "12865번 - 평범한 배낭" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

12865번: 평범한 배낭

---

소스 코드

#include <stdio.h>

int max(int a, int b);

int main(void){
    int N, K;
    scanf("%d %d", &N, &K);

    int objects[N][2];
    for(int i=0; i<N; i++){
        scanf("%d %d", &objects[i][0], &objects[i][1]);
    }

    int value[N+1][K+1];
    //value[i][j] : 첫 i개의 물건으로 j 이하의 무게를 만들 때 최대 가치합
    //최종 답: value[N][K]
    for(int i=0; i<N+1; i++){
        value[i][0] = 0;
    }
    for(int i=0; i<K+1; i++){
        value[0][i] = 0;
    }
    for(int i=1; i<N+1; i++){
        for(int j=1; j<K+1; j++){
            if(objects[i-1][0]>j)
                value[i][j] = value[i-1][j];
            else{
                value[i][j] = max(value[i-1][j], value[i-1][j-objects[i-1][0]] + objects[i-1][1]);
            }
        }
    }

    /*
    printf("  ");
    for(int j=0; j<K+1; j++){
        printf("%d ", j);
    }
    printf("\n");
    for(int i=0; i<N+1; i++){
        printf("%d ", i);
        for(int j=0; j<K+1; j++){
            printf("%d ", value[i][j]);
        }
        printf("\n");
    }
    */

    printf("%d\n", value[N][K]);
}

int max(int a, int b){
    if(a>b)
        return a;
    else
        return b;
}

---

문제 풀이

  정해진 무게를 넘지 않게 배낭에 최대한 물건을 담는 동적 계획법 문제, '배낭 문제 (Knapsack Problem)'입니다.

  우선 입력 첫 줄은 물품의 수 N과 버틸 수 있는 무게 K이므로, 이들을 각각 변수 N과 K에 저장합니다. 그 후 두 번째 줄부터 차례로 나오는 각 물건의 무게 W와 가치 V를 저장하기 위해 배열 'objects'를 선언합니다. 배열 'objects'는 크기가 N × 2 이므로, N개 물건들의 W와 V를 각각 저장하기에 충분합니다. Line 10 ~ 12의 for문은 차례로 'objects' 배열을 채우는데, i번째 물건의 W는 objects[i][0]에, V는 objects[i][1]에 저장되어 접근하기가 쉽습니다.

  Line 14의 배열 'value'는 최종 답을 구하기 위해 앞으로 저희가 채워야할 배열입니다. 구체적으로, value[i][j]는 첫 i개의 물건으로 j 이하의 무게를 만들 때 최대 가치합입니다. 예를 들어, value[2][3]의 값은 첫 두 개의 물건으로 3 이하의 무게를 만들 때 나올 수 있는 최대 가치합이고, value[4][12]는 첫 네 개의 물건으로 12 이하의 무게를 만들 때 최대 가치합입니다. 그렇다면, 배열의 마지막 요소인 value[N][K]는 어떤 의미를 가질까요? 첫 N개의 물건으로 K 이하의 무게를 만들 때 나올 수 있는 최대 가치합을 의미합니다. 저희에게 주어진 총 물품의 수가 N개이고 준서가 버틸 수 있는 무게가 K이므로, 결국 value[N][K]가 구하고자 하는 정답인 셈입니다.

  차근차근 코드를 살펴봅시다. Line 17 ~ 19는 value[0][0], value[1][0], ... , value[N][0]의 값을 0으로 만듭니다. 그 이유는, value[i][0]은 첫 i개의 물건으로 0 이하의 무게를 만든다는 의미인데 모든 물건의 무게가 1 이상이므로 물건을 넣지 않는다는 것과 똑같기 때문입니다. 당연히 물건을 넣지 않으면, 가치합의 최댓값도 0이 되겠죠?

  마찬가지로, Line 20 ~ 22는 value[0][0], value[0][1], ... , value[0][N]의 값을 0으로 만듭니다. value[0][i]은 첫 0개의 물건으로 i 이하의 무게를 만든다는 의미인데, 어떠한 물건도 선택하지 않을 경우 가치합도 0이기 때문입니다.

  마지막으로 Line 23 ~ 31은 배열의 남은 칸들을 차례로 채우는 부분입니다. 즉, value[i][j]를 i와 j가 작은 값부터 채워나가는데, 채우는 알고리즘이 다음과 같습니다.

목표: value[i][j]에 들어갈 값 구하기

1. i번째 물건의 무게를 의미하는 objects[i-1][0]을 불러온 후, 이것이 j보다 큰지 확인합니다.

2. 만약 i번째 물건의 무게 (objects[i-1][0]) 가 j 보다 크다면, value[i][j]의 값은 value[i-1][j]의 값과 같습니다.
이유: value[i][j]는 '첫 i개의 물건으로 j 이하의 무게를 만드는 것'이고, value[i-1][j]는 '첫 i-1개의 물건으로 j 이하의 무게를 만드는 것'입니다. 따라서 value[i][j]와 value[i-1][j]의 차이는, j 이하의 무게를 만들 때 i번째 물건을 고려하냐 고려하지 않냐의 차이입니다. 만약 i번째 물건의 무게가 j 보다 크다면, j 이하의 무게를 만들 때 사용되지 못하므로 고려할 필요가 없고, 결론적으로 value[i][j]와 value[i-1][j]는 첫 i-1개의 물건으로 j 이하의 무게를 만든다는 상황 자체가 똑같아집니다.

3.  만약 i번째 물건의 무게 (objects[i-1][0]) 가 j 보다 크지 않다면, value[i][j]의 값은 value[i-1][j]의 값과 value[i-1][j-objects[i-1][0]] + objects[i-1][1]의 값 중에서 큰 값이 됩니다.
이유: i번째 물건의 무게가 j 보다 크지 않다면, j 이하의 무게를 만들 때 i번째 물건을 사용할 수도 있다는 이야기가 됩니다. 이럴 경우, i번째 물건을 사용하는게 이득인지, 사용하지 않는게 이득인지 따져봐야겠죠? 우선 value[i-1][j]는 i번째 물건을 사용하지 않았을 때의 최대 가치합입니다. i번째 물건을 무시한 채, 첫 i-1개의 물건만 사용하는 경우이기 때문이죠. value[i-1][j-objects[i-1][0]] + objects[i-1][1]은 i번째 물건을 사용했을 때의 최대 가치합입니다. 첫 i-1개의 물건으로 j에서 i번째 물건의 무게만큼 뺀 값을 만들 때의 최대 가치합과 i번째 물건의 가치만큼 더해주면, i번째 물건을 반드시 사용했을 때의 최대 가치합이 얻어집니다. 이 값과 앞서 구한 value[i-1][j]의 값을 비교하여 더 큰 값을 이용하면, 첫 i개의 물건으로 j 이하의 무게를 만들 때 최대 가치합을 구할 수 있습니다.

  이 모든 과정을 거치면, 최종적으로 value[N][K]를 얻을 수 있습니다. N개의 물건으로 K 이하의 무게를 만들 때의 최대 가치합은 곧 출력하고자 하는 결과이므로, 이를 출력함으로써 문제를 해결할 수 있습니다.