[알고리즘 정리] 배낭 문제(Knapsack Problem)

Knapsack Problem

Knapsack Problem, 배낭문제는 다이나믹 프로그래밍에서 매우 유명한 문제이다.
어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게가 K라고 하자. 배낭에 넣을 수 있는 N개의 물건이 각기 다른 가치 V를 가지고 있고 각 물건마다 다른 무게 W를 가지고 있을 때, 배낭이 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제이다. 냅색 문제는 Fractional Knapsack, 즉 물건을 쪼갤 수 있어 무게나 가치가 소수점 단위로 나뉘는 문제, 또는 0-1 Knapsack 물건을 쪼갤 수 없어 무게와 가치가 무조건 정수형태를 가지는 두 유형으로 나뉜다. 이번에는 0-1 Knapsack 문제를 해결하는 방법에 대해서 생각해보자.

Brute Force Approach

만약 n개의 물건이 있을 때, 가능한 모든 조합을 만들기 위해서는 2ⁿ 개의 경우의 수를 모두 시도해 보아야한다. 가지고 있는 물건이 몇개 없다면 별로 시간이 오래걸리지는 않겠지만, 2ⁿ 은 물건의 갯수가 하나만 늘어도 경우의 수가 크게 늘어나게 된다. 이 연산을 수행하려면 𝛩(2ⁿ ) 의 시간을 사용해야하고, 프로그래머 입장에서 그다지 좋은 접근은 아닐 것이다.

Dynamic Programming

따라서 이 문제는 당연스럽게도 다이나믹 프로그래밍으로 해결해야 한다. 그런데 항상 그렇듯 DP 의 가장 큰 어려움은 subproblem 을 정의하는 것이 쉽지 않다는 것이다. 나도 그랬고 많은 사람들이 이 문제의 subproblem 을 찾기 위해 다음과 같이 생각했을 것이다.

Finding Subproblem - 1

• 무게 7의 가방을 최대 가치로 가득 채우려면 무게 6일때 최대 가치로 가득 채웠을 때의 조합에 하나가 더 들어갈 수 있는지 확인해보면 되지 않을까?

이 수업을 듣기전에 나도 이렇게 생각했고 이 접근으로 문제를 풀어보려고 몇시간을 고민했던 적도 있다. 하지만 이 접근은 subproblem을 만들어내지 못한다. 기존에 있던 조합에서 하나의 물건을 빼고 다른 하나를 넣는 것으로 최대가치를 만들수 있기 때문이다. 따라서 무게 4일 때의 조합과 무게 5일때의 조합이 달라질 여지가 충분히 있는 것이다.

Finding Subproblem - 2

위 접근이 아닌 다른 방법으로 어떻게 접근해야 할까. 배낭에 물건을 넣을 때, 우리가 선택할 수 있는 경우는 두 가지가 있다.

1. 물건을 넣는다.
2. 물건을 넣지 않는다.

만약 현재 내가 넣으려고 하는 물건의 무게가 전체 제한무게를 초과한다면, 선택지는 물건을 넣지 않는 것 밖에 없다. 따라서 다음과 같은 식을 일단 하나 만들 수 있다.

B[k][W] = B[k-1][W], if w_k > W

 

B는 DP를 위한 최대가치를 담는 배열이고, k는 현재 넣은 물건의 번호, W은 최대 무게를 의미한다. w_k 는 k번째 물건에 대한 무게를 의미한다. 따라서 위 식은 k번째 물건이 총 제한 무게를 초과한다면 k번째 최대가치를 바로 k-1번째 물건을 넣을 경우의 가치로 정하는 것이다.

만약 물건을 넣을 수 있는 무게가 조금이라도 남았다면 어떻게 해야할까? 이때 우리의 선택지는 다시 두 가지로 나뉜다.

1. 새로운 물건을 넣지 않는다
2. 새로운 물건을 넣기 위해 현재 물건을 넣을 공간을 만들어서 물건을 넣는다.

우리는 최대 가치를 원하기 때문에, 두 경우 중 더 큰 값을 선택하게 될 것이다. 이것을 수식으로 만들면,

B[k][W] = max(B[k-1][W], B[k][W-w_k] + val(w_k))

 

현재 물건을 넣기 위해 넣었던 물건을 뺐을 때의 가치에 현재 물건의 가치를 더해주면 된다.

 

표를 채워가면서 더 자세하게 생각해보자. 우리에게 네 개의 물건이 있다고 하자 물건은 (무게, 가치) 로 나타내겠다. 그리고 물건을 넣을 가방의 최대 무게는 5라고 하자.

물건 : (2, 3), (3, 4), (4, 5), (5, 6)
가방의 최대 무게: 5

 

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0
1
2
3
4
5

• 위와 같은 테이블을 만들고, 행은 최대 무게, 열은 물건의 번호를 가르키도록 하자.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0
2	0
3	0
4	0
5	0

• 최대 무게가 0일 때, 그리고 물건이 없을 때는 가방에 넣을 수 있는 최대 가치는 당연히 0이다. 따라서 첫 행과 첫 열은 0으로 모두 채워줄 수 있다.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0	0
2	0
3	0
4	0
5	0

• 일단 첫 물건을 생각해보자. 무게 2, 가치 3짜리 물건이다. 이 물건을 가지고 해당 물건이 각 최대 무게당 가지는 최대 가치를 따져보면, 최대 무게가 1일 때는 현재 물건의 무게가 2이기 때문에 넣을 수 없다. 따라서 0을 넣어준다.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0	0
2	0	3
3	0
4	0
5	0

• 최대 무게가 2일 때는 현재 물건의 무게가 2이기 딱 맞게 물건을 넣을 수 있다. 물건을 넣게 되면 최대 가치는 3이 된다. 따라서 1열의 2행에는 1번째 물건의 가치인 3을 넣어준다.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0	0
2	0	3
3	0	3
4	0	3
5	0	3

• 첫번째 물건을 넣게 되면, 다른 모든 최대 무게에 대해서는 한번씩 모두 들어간다고 봐야한다. 무게가 2이니까 최대 무게가 3일 때도, 4일 때도, 5일 때도 하나씩 넣을 수 있기 때문이다. 따라서 1열의 남은 행은 모두 3으로 채워줄 수 있다.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0	0	0
2	0	3	3
3	0	3
4	0	3
5	0	3

• 다음 물건으로 넘어가보자. 다음은 (3, 4) 이다. 일단 무게가 3이기 때문에 가방의 최대무게가 3이 될 때 까지는 이 물건을 넣을 수 없다. 따라서 위와 같이 3미만의 무게에 대해서는 모두 1번째 물건을 넣은 상태로 두는 것이 가장 좋다.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0	0	0
2	0	3	3
3	0	3	4
4	0	3
5	0	3

• 자 이제 본격적으로 머리를 굴려볼 때가 왔다. 최대 무게가 3이 되었을 때는 우리에게 두 가지 선택지가 있다고 설명했었다. 넣거나, 넣지 않거나.
• 이 물건을 넣는다고 생각해보자. 그런데 물건을 넣게 되면 가방의 최대 무게를 초과하게 된다. 왜냐하면 이 시점에서는 가방에 첫번째 물건이 들어있기 때문이다. 따라서 물건을 넣으려면 이미 들어있는 첫번째 물건을 빼고 현재 물건을 넣어줘야한다. 가방에 있는 물건을 빼고 새 물건을 넣는다면, 가방의 최대 가치는 두 번째 물건의 가치인 4가 된다.
• 물건을 넣지 않는다고 생각해보자. 가방 안에는 첫 번째 물건이 들어있기 때문에 가방의 최대 가치는 3이 된다.
• 우리는 가방안에 들어있는 물건들의 가치를 최대로 하고 싶다. 따라서 우리가 선택할 선택지는 물건을 넣어서 가치가 4가 되게 하는 것이다.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0	0	0
2	0	3	3
3	0	3	4
4	0	3	4
5	0	3	7

• 가방의 최대 무게가 4일 때 역시 2번째 물건을 넣는 것이 이득이다.
• 가방의 최대 무게가 5일 때는 어떨까? 첫번째 물건을 넣은 상태에서 현재 물건을 넣어도 가방의 무게가 초과되지 않는다. 따라서 최대 무게가 5인 경우에는 두 물건을 모두 넣는것이 최대 가치를 만드는 선택일 것이다.

	0	1 (2, 3)	2 (3, 4)	3 (4, 5)	4 (5, 6)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	3	3	3	3
3	0	3	4	4	4
4	0	3	4	5	5
5	0	3	7	7	7

• 위 작업을 모든 물건에 대해서 진행해보자. 우리는 위와 같은 표를 얻을 수 있고, 최대 무게 5에 대한 최대 가치는 7이라는 것을 알 수 있다.
• 어떤 조합으로 최대 가치에 이르렀는지는 해당 가치값이 최초로 나온 지점을 보면된다. 이 경우에서는 1번째 물건과, 2번째 물건을 가방에 넣고 나머지 물건은 가방에 넣지 않는 경우가 최대 가치를 만드는 경우이다.

Pseudo code

위 로직을 pseudo code로 적어보자.

for w = 0 to W
    B[0][W] = 0
for i = 1 to n
    B[i][0] = 0
    for w = 1 to W
    if w[i] <= w
        if b[i] + B[i-1][w-w[i]] > B[i-1][w]
            B[i][w] = b[i] + B[i-1][w-w[i]]
        else B[i][w] = B[i-1][w]
    else
        B[i][w] = B[i-1][w]

책에 나와있는 코드인데 변수가 무엇을 의미하는지 정확히 안나와 있어서 잘 와닿지 않는다. 백준에 동일한 알고리즘 문제가 있으니 [백준 알고리즘] 문제를 풀어보자. vector, pair, 같은 컨테이너나 algorithm에 들어있는 max 함수를 사용하면 더 수월하겠지만 최대한 pseudo code랑 비슷하게 만들었다. PS 포스트는 STL로 더 깔끔한 코드로 만들어서 올려보자.

implementation - BOJ 12865

문제
이 문제는 아주 평범한 배낭에 관한 문제이다.

 

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

 

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

#include <cstdio>

#define WEIGHT 0
#define VALUE 1

using namespace std;

int main()
{
    int dp[101][100001] = {0, };
    int item[101][2];

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

    for (int i = 1; i <= N; i++){
        scanf("%d %d", &item[i][WEIGHT], &item[i][VALUE]);
    }

    for (int i = 1 ; i <= N ; i++){
        for (int w = 1 ; w <= K ; w++){
            if (item[i][WEIGHT] <= w){ // 최대 무게를 하나씩 올려가면서 계산
                if ((item[i][VALUE] + dp[i-1][w-item[i][WEIGHT]]) > dp[i-1][w]) // 이전 최대가치를 사용하는 것보다 이전걸 빼고 현재물건을 넣는게 더 좋다면 넣어주자
                    dp[i][w] = item[i][VALUE] + dp[i-1][w-item[i][WEIGHT]];
                else dp[i][w] = dp[i-1][w]; // 아니라면 이전가치를  그대로 사용
            }
            else{
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    printf("%d", dp[N][K]);
    return 0;
}

Algorithm Analysis

DP 로 접근한 Knapsack Problem의 time complexity는 단순하게 2차원 배열을 모두 채워주면 끝나기 때문에, 무게 W, 물건의 갯수 N에 대해 Օ(NW) 의 시간복잡도를 가진다.