Chap 5-1. 0-1 배낭 문제

0, 1 배낭 문제

조건

1. 4kg을 담을 수 있는 배낭
2. 넣을 수 있는 물건 A, B, C가 있다.
3. B의 무게 = 4, 가치 = 30
4. C의 무게 = 3, 가치 = 20
5. A의 무게 = 1, 가치 = 15

가장 단순한 방법은 모든 물건의 조합을 시도를 해서 총 가치를 구한 다음에 가장 가치가 높은 경우를 선택하는 것이다. 이렇게 한다면 지수 시간의 시간 복잡도를 갖는 문제이다. 2^n의 경우의 수이다.

이 문제를 (1) 재귀 방법으로 풀 수 있고 (2) DP방법으로도 풀어볼 수 있다.

 

 

(1) 재귀 방법

#include <stdio.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))


int knapSack(int W[], int V[], int n, int c)
{
    if(n <= 0 || c <= 0)//더 이상 물건이 없거나 용량이 더 이상 남아있지 않다면 
        return 0;
    if(W[n-1] > c) // 담을 수 없으니까
        return knapSack(W, V, n-1, c); //다음 번 물건으로 넘어간다. 
    
    
    // n번째 물건을 배낭에 넣는 경우  -> 다음 물건으로 넘어감, 배낭 수용 무게 줄어듦, 가치 올라감 
    int carry = V[n-1] + knapSack(W, V, n-1, c - W[n-1]);
    int leave = knapSack(W, V, n-1, c);// n번째 물건을 가져가지 않는 경우 -> 가치는 증가하지 않음, 다음 물건으로 넘어감
    printf("%d %d\n", carry, leave);
    return MAX(carry, leave);
}

int main()
{
    int W[3] = {1, 4, 3};
    int V[3] = {15, 30, 20};

    printf("%d\n", knapSack(W, V, 3, 4)); // 가방의 무게, 가치, 물건의 개수, 배낭 용량

    return 0;
}

 

(2) 동적 계획 방법

먼저 테이블(격자)을 그린다.

1kg, 2kg, 3kg, 4kg는 무게에 대한 배낭의 크기를 의미

A, B, C는 물건의 종류이다. 물건과 무게의 경우의 수를 고려하여 최적의 답을 구해야 하기 때문이다.

격자는 해당 상황에서 가장 Value가 높은 값을 채우는 것이다.

격자를 모두 채우면 답이 나온다.

DP방법으로 격자를 모두 채운 모습

 

[채우는 과정]

위의 격자는 (넣을 수 있는 Weight, 물건 종류)로 표현했다. 

A, B, C행를 기준으로 차례대로 경우의 수를 따질 것인데 이 때, A행은 A행만, B행은 A + B행, C행은 A+B+C행을 고려한다. 이때, 순서를 바꾸어도 결과는 일치한다.

 

먼저 A행부터 보자. <이 때, A 물건만 생각하는 것이다>

(A, 1)이라는 것은 "배낭이 1kg인데 A 물건을 넣을 수 있느냐?"의 의미이다. A 물건은 1kg이므로 넣을 수 있으며 A의 Value는 15이므로 해당 자리에 15를 넣는다. 

 

(A, 2)이라는 것은 "배낭이 2kg인데 A 물건을 넣을 수 있느냐?"의 의미이다. A 물건은 1kg이므로 넣을 수 있으며 A의 Value는 15이므로 해당 자리에 15를 넣는다.

 

(A, 3)이라는 것은 "배낭이 3kg인데 A 물건을 넣을 수 있느냐?"의 의미이다. A 물건은 1kg이므로 넣을 수 있으며 A의 Value는 15이므로 해당 자리에 15를 넣는다.

 

(A, 4)이라는 것은 "배낭이 4kg인데 A 물건을 넣을 수 있느냐?"의 의미이다. A 물건은 1kg이므로 넣을 수 있으며 A의 Value는 15이므로 해당 자리에 15를 넣는다.

 

자 이제 B행을 살펴보자. B행은 A행을 고려하여 생각하는 것이다. 

(B, 1) 이라는 것은 "배낭이 1kg이며 A 물건과 B물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. B 물건은 4kg이므로 1kg 배낭에 넣을 수 없다. 따라서 A의 Value인 15를 해당 자리에 입력한다. ("위의 열의 값이 내려온다"라고 표현)

 

(B, 2) 이라는 것은 "배낭이 2kg이며 A 물건과 B물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. B 물건은 4kg이므로 2kg 배낭에 넣을 수 없다. 따라서 A의 Value인 15를 해당 자리에 입력한다. ("위의 열의 값이 내려온다"라고 표현)

 

(B, 3) 이라는 것은 "배낭이 3kg이며 A 물건과 B물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. B 물건은 4kg이므로 3kg 배낭에 넣을 수 없다. 따라서 A의 Value인 15를 해당 자리에 입력한다. ("위의 열의 값이 내려온다"라고 표현)

 

(B, 4) 이라는 것은 "배낭이 4kg이며 A 물건과 B물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. B 물건은 4kg이다. A 물건과 B 물건을 넣을 수 있는 경우의 수는 A만 넣기, B만 넣기 그리고 A와 B 모두 넣기가 있다. A와 B 물건을 모두 넣는 경우는 배낭의 크기가 4kg이므로 불가능하다. (A와 B 모두 넣으면 1+4 = 5kg이다) 하지만 A만 넣기는 해당 물건을 넣으려면 1kg만 필요하므로 배낭에 넣는 것이 가능하고 B만 넣기도 해당 물건을 넣으려면 4kg가 필요하므로 배낭에 넣는 것이 가능하다. 

이제 A만 넣기 vs B만 넣기 중 value가 더 높은 것을 선택하면 된다. A만 넣는 것은 value가 15이지만 B만 넣는 것은 value가 30이므로 B만 넣는 것을 채택한다. 그리고 해당 value인 30을 격자에 넣는다. 

 

마지막으로 C행을 보자.

(C, 1)이라는 것은 "배낭이 1kg이며 A 물건, B물건, C물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. B 물건은 4kg이고 C물건은 3kg이므로 1kg 배낭에 넣을 수 없다. 따라서 A의 Value인 15를 해당 자리에 입력한다. ("위의 열의 값이 내려온다"라고 표현)

 

(C, 2)이라는 것은 "배낭이 2kg이며 A 물건, B물건, C물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. B 물건은 4kg이고 C물건은 3kg이므로 1kg 배낭에 넣을 수 없다. 따라서 A의 Value인 15를 해당 자리에 입력한다. ("위의 열의 값이 내려온다"라고 표현)

 

(C, 3)이라는 것은 "배낭이 3kg이며 A 물건, B물건, C물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. 먼저 B물건은 4kg이므로 3kg짜리 배낭에 넣을 수 없다. 하지만 A물건과 C물건은 각각 1kg, 3kg이므로 3kg 배낭에 넣을 수 있다. 그러므로 A 물건과 C 물건중 어떤 물건을 넣어야 가치가 큰 지 비교하면 된다. A 물건은 value가 15이고 C물건은 value가 20이므로 C물건을 배낭에 넣는 것이 더 가치가 높으므로 격자에 20을 채운다. 

 

(C, 4)이라는 것은 "배낭이 3kg이며 A 물건, B물건, C물건을 어떻게 조합하여 넣으면 가장 높은 가치를 넣을 수 있을까?"라는 의미이다. 여기서 가능한 경우는 

(1) A물건 + C물건 넣기 ( 1 kg + 3kg = 4kg 배낭에 넣을 수 있다.) => value : 35

(2) A물건만 넣기 => value : 15

(3) B물건만 넣기 => value : 30

(4) C물건만 넣기 => value : 20

가치가 가장 높은 것은 A물건 + C물건 넣기 경우이므로 value 35를 격자에 넣는다. 

 

따라서, 모든 조합을 시도했더니 가장 가치가 높은 경우는 A물건과 C물건을 넣는 것임을 알 수 있다.

 

[DP 방법 코드 구현]

#include <stdio.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))


//이 문제에서 배낭의 용량과 물건 이렇게 2개의 변수가 존재한다. -> 각 행이 물건의 종류 , 각 열이 배낭의 용량 -> 2차원 grid로 저장 
void knapSack(int W[], int V[], int n, int c)
{
    int cell[n + 1][c + 1]; //배낭의 무게가 0일 때, 용량도 0일 때를 저장해야 한다. (추가적 필요)

    for (int i = 0; i <= n; i++) //각각 0으로 초기화한다. 
        cell[i][0] = 0;
    for (int j = 0; j <= c; j++)
        cell[0][j] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            if (W[i - 1] <= j) //배낭 안에 들어올 수 있으면
            {
                int x = j - W[i - 1]; //배낭의 남은 공간 계산
                cell[i][j] = MAX(cell[i - 1][j], V[i - 1] + cell[i - 1][x]);//자기 자신의 값이나 남은 공간의 위치



            }
            else //배낭에 들어올 수 없다면 
                cell[i][j] = cell[i - 1][j]; //위의 것이 그대로 내려옴

        }
    }
    for (int i = 0; i <= n; i++)//격자 출력
    {
        for (int j = 0; j <= c; j++)
            printf("%2d", cell[i][j]);
        printf("\n");
    }
}

int main()
{
    int W[3] = { 1, 4, 3 };
    int V[3] = { 15, 30, 20 };

    knapSack(W, V, 3, 4); // 가방의 무게, 가치, 물건의 개수, 배낭 용량

    return 0;
}