Home Knapsack Problem
Post
Cancel

Knapsack Problem

By Joe2357
Posted 2023-01-30 Updated 2024-02-16 13 min read

배낭 채우기 알고리즘

냅색이란?

1
2
3
4
5

한 여행가가 가지고 가는 배낭이 있다. 배낭에 담을 수 있는 무게의 최댓값은 W이다.  
여행가는 여행을 가기 위해 필요한 짐들을 배낭에 넣어 가지고 갈 계획을 세우고 있다.  
각 짐들은 일정한 무게와 가치를 지니고 있다.
여행자는 이 짐들을 배낭에 최대한 넣어 가치의 합이 최대가 되도록 짐을 싸려고 한다.  
어떻게 하면 여행자가 가진 배낭을 이용하여 최대의 가치를 얻을 수 있을까?

배낭 문제 (Knapsack Problem) 은 위의 문제와 같이 주어진 용량에서 최대의 가치를 얻을 수 있도록 물건을 고르는 문제를 말한다. 문제의 조건에 따라 2가지 문제로 나눌 수 있다.

  • 물건을 잘라 가질 수 있는 경우 : Fractional Knapsack (물건의 무게가 소수일 수 있다)
  • 물건을 잘라 가질 수 없는 경우 : 0-1 Knapsack (물건의 무게가 소수일 수 없다)

알고리즘 문제로는 주로 후자인 “0-1 Knapsack” 문제를 주로 다룬다. Fractional 같은 경우, 일반적인 greedy한 방법으로 쉽게 답을 구할 수 있기 때문이다. 간단하게 무게 대비 가치가 가장 높은 것부터 최대한 잘라 배낭에 넣으면 가장 가치가 높을 것임이 자명하다.

0-1 냅색같은 경우, 물건을 선택할지 선택하지 않을지를 이용하여 배낭에 넣을 물건의 조건을 탐색할 수 있을 것이다. 일반적으로 아래와 같은 방법이 가장 먼저 떠오를 것이다.

  • 모든 경우의 수를 탐색 (브루트포스)
    • 각 물건을 넣을지 말지 선택하는 경우는 총 2가지, 물건이 N개라면 총 $2^N$개의 선택지가 존재한다.
    • 결국 시간복잡도가 $O(2^N)$에 달하기 때문에 시간상 불가능한 방법
  • 무게 대비 가치가 높은 물건부터 넣기 (그리디)
    • 시간에는 돌지 몰라도, 최적의 답을 보장하지 않는다는 문제점이 있음
    • 하나의 가치가 큰 물건을 넣는 것보다, 작은 물건 여러개를 넣는 것이 “배낭의 공간을 효율적으로 사용”할 수 있는 가능성이 있기 때문

위 2개의 방법이 둘 다 되지 않는다면 어떻게 냅색문제를 해결할 수 있을까?

알고리즘 해법

이 단계에서는 냅색 문제를 해결하기 위해, 문제 예시와 그 해법에 대해 설명한다.

시나리오 예시

문제는 백준의 “12865 - 평범한 배낭” 문제에서의 예제를 이용한다. 조건은 아래와 같다.

  • 물건의 개수 $N = 4$

  • 배낭의 용량 $K = 7$

  • 각 물건의 무게, 가치

    번호무게가치
    1613
    248
    336
    4512

DP를 이용한 방법

dp는 ‘이전의 상태를 미리 기록해두었다가 이후의 큰 문제를 풀 때 이전의 값을 활용’하는 방법이다. dp문제는 항상 “어떤 subproblem의 답을 저장할 것인지” 확정하는 것이 어려운데, 냅색에서는 아래와 같이 정의할 수 있다.

dp[i][j] : 배낭의 용량이 j일 때, i번째 물건까지 고려하였을 때 배낭에 넣을 수 있는 물건들의 가치의 최대 합

이렇게 지정하면 문제에서 원하는 답은 dp[N][K]에 존재하게 될 것이다. 배낭의 용량이 $K$일 때 $N$개의 모든 물건을 고려하였을 경우를 생각해야하기 때문이다.

활용하기 위한 점화식을 구해야한다. 문제에서 원하는 답이 배열의 제일 끝에 위치하기 때문에, 배열의 처음부터 값을 채워나가는 bottom-up 방식을 사용해야할 것 같다. 생각해보면 dp[i][j]는 $i-1$번째 물건까지 모두 배낭에 넣은 이후에 $i$번째 물건을 넣을지 말지 결정하는 문제로 쪼개 생각할 수 있을 것 같다. $i$번째 물건의 무게를 $w[i]$, 가치를 $v[i]$라고 할 때, dp[i][j]는 아래와 같은 수식으로 지정할 수 있을 것 같다. \(dp[i][j] = \begin{cases} dp[i-1][j] & \text{물건을 넣을 용량이 없는 경우} \\ \max (dp[i-1][j], dp[i-1][j-w[i]] + v[i]) & \text{물건을 넣을 수 있는 용량이 있는 경우} \end{cases}\) 물건을 넣을 수 있는 용량이 없는 경우, dp배열에서 index가 음수가 되는 경우가 되기 때문에 참조할 수 없는 상황이 발생한다. 따라서 그냥 max하면 안되고, 배낭에 현재 물건을 넣을 수 있는지 확인하는 과정이 필요하다. 이 점화식을 모든 배열의 칸에 적용하면 된다. (배열의 기본값은 $0$이라는 점을 기억하자)

시나리오 예시를 통해 이해해보자. 아래와 같은 표를 채워나가는 것이 dp의 목적이다.

dp[][]01234567
000000000
100000000
200000000
300000000
400000000

먼저 dp[0][]을 보자. 첫번째 index가 0이라는 것은 어떤 물건도 배낭에 넣는 것을 고려하지 않았다는 의미이다. 그렇다면 당연히 모든 상황에서 가치의 합은 0이 될 것이다. 값의 변동이 없다.

dp[][]01234567
000000000
100000000
200000000
300000000
400000000

첫번째 물건을 고려해보자. 첫번째 물건은 무게가 $6$, 가치가 $13$이다. 일단 배낭의 용량이 $6$인 배낭부터 이 물건을 고려할 수 있을 것이다. 점화식에 맞춰 생각해보자. dp[1][6] = max(dp[1-1][6], dp[1-1][6-6] + 13), dp[1][7] = max(dp[1-1][7], dp[1-1][7-1] + 13) 으로 생각할 수 있을 것이다. 이것을 말로 풀어쓰면 “현재 배낭의 용량에서 물건을 선택하였을 때와 선택하지 않았을 때 중 가치의 최댓값이 될 수 있는 것” 이라고 생각하면 된다. 위 값으로 채워넣자.

dp[][]01234567
000000000
10000001313
200000000
300000000
400000000

이런 방식으로 모든 물건에 대해 값을 채워넣을 수 있다. 나머지는 스스로 해보자. 최종 결과는 아래 표와 같다.

dp[][]01234567
000000000
10000001313
20000881313
30006881314
400068121314

문제의 정답은 dp[N][K] = dp[4][7]에 존재할 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <stdio.h>

typedef struct Node {
    int w, v;
} ND;

#define MAX_IDX 100
#define MAX_WEIGHT 100001

int dp[MAX_IDX + 1][MAX_WEIGHT + 1];
ND item[MAX_IDX + 1];
int n, k;

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

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &item[i].w, &item[i].v);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (item[i].w <= j) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - item[i].w] + item[i].v);
            }
        }
    }

    printf("%d", dp[n][k]);
    return 0;
}

배열의 크기가 너무 크다고 생각된다면 배열을 2차원이 아닌 1차원으로 하는 방법도 존재한다. 슬라이딩 윈도우처럼 배열의 $i$번째 가로줄만을 저장하는 방법을 사용하는 것이다. 그렇게 한다면 배열의 크기를 $N$배만큼 줄일 수 있고, 시간 또한 절약할 수 있다. 다만 이 때는 배열의 적은 index값을 활용하는 경우이므로, 배열의 index를 뒤부터 채워야한다는 조건이 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <stdio.h>

typedef struct Node {
    int w, v;
} ND;

#define MAX_IDX 100
#define MAX_WEIGHT 100001

int dp[MAX_WEIGHT + 1];
ND item[MAX_IDX + 1];
int n, k;

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

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &item[i].w, &item[i].v);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = k; j > 0; --j) {
            if (item[i].w <= j) {
                dp[j] = max(dp[j], dp[j - item[i].w] + item[i].v);
            }
        }
    }

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

백트래킹을 이용한 방법

  • 추후 서술, 최적화가 되어있지 않음
Storage, Algorithm
Algorithm
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents