[알고리즘] 배낭 문제, Knapsack Problem

배낭 문제 (Knapsack Problem)

---

배낭 문제란,

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때

가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

 

배낭 문제에는 2가지 경우가 있다.

1. 분할 가능 배낭 문제 (Fractional Knapsack Problem) - 짐을 쪼갤 수 있는 경우

2. 0-1 배낭 문제 (0-1 Knapsack Problem) - 짐을 쪼갤 수 없는 경우

 

 

짐을 쪼갤 수 있는 경우에는 그리디 알고리즘을 통해 해결할 수 있다.

(가치가 가장 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식)

 

 

짐을 쪼갤 수 없는 경우에는 동적 계획법(Dynamic Programming, DP)을 통해 해결할 수 있다.

브루트 포스로도 해결할 수 있겠지만, 시간 복잡도가 O(2^n)으로 너무 크기 때문에 DP로 해결해야 한다.

 

 

본 글에서는 0-1 배낭 문제 해결법에 초점을 두도록 하겠다.

 

0-1 배낭 문제 (0-1 Knapsack Problem)

* 참고

12865번: 평범한 배낭

 

4가지의 물품 A, B, C, D가 있고, 각 물건의 무게와 가치는 아래의 표와 같다고 하자.

배낭에 최대로 넣을 수 있는 무게는 7이다.

 

	무게	가치
A	6	13
B	4	8
C	3	6
D	5	12

 

 

* 동적 계획법 문제 해결의 순서 : 테이블 정의 → 점화식 찾기 → 초기값 정하기

 

 

1. 테이블 정의

(물품의 개수+1) × (배낭에 최대로 넣을 수 있는 무게+1) 크기의 배열을 생성할 것이다.

dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]	# K : 최대 무게 / N : 물건의 개수

 

	0	1	2	3	4	5	6	7
0
1
2
3
4								🐻

 

행 i는 i번째 물건까지 배낭에 넣을 수 있음을 의미하고,

열 j는 배낭에 무게 j까지 넣을 수 있을 경우 만들 수 있는 최대 가치의 합이다.

 

즉, dp[i][j]가 의미하는 것은 i번째 물건까지 배낭에 넣을 수 있을 때, 무게 j 이하가 되는 물건들의 최대 가치 합이다.

 

우리가 최종적으로 구해야 하는 것은 위의 배열 상에서 🐻이 있는 부분이다.

 

 

2. 점화식 찾기

먼저 배열을 채우는 과정을 찬찬히 살펴보자.

 

(1) 첫 번째 물건 A만 배낭에 넣을 수 있을 때, 배낭의 최대 무게에 따른 최대 가치의 합은 다음과 같다.

* A의 무게 : 6 / 가치 : 13

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2
3
4

 

 

(2) 두 번째 물건까지 배낭에 넣을 수 있을 때, 배낭의 최대 무게에 따른 최대 가치의 합은 다음과 같다.

* A의 무게 : 6 / 가치 : 13

* B의 무게 : 4 / 가치 : 8

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3
4

 

 

(3) 세 번째 물건까지 배낭에 넣을 수 있을 때, 배낭의 최대 무게에 따른 최대 가치의 합은 다음과 같다.

* A의 무게 : 6 / 가치 : 13

* B의 무게 : 4 / 가치 : 8

* C의 무게 : 3 / 가치 : 6

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4

 

여기서 3행 4열과 3행 7열을 주의 깊게 보자.

3행 4열에서는 배낭에 C만 넣는 경우보다 A와 B를 넣는 것이 가치합이 더 크기 때문에 (6 < 8) 8이 저장되었다.

 

3행 7열에서는 배낭에 B+C를 넣는 것이 A 하나를 넣는 것보다 가치합이 크기 때문에 (14 > 13) 14가 저장된 것이다.

 

이때 14는 'C의 가치 + 배낭의 최대 무게가 4일 때의 최대 가치합'과 같다.

배낭의 최대 무게가 7일 때 C를 넣고도 가방의 무게가 4가 남기 때문이다.

 

 

(4) 네 번째 물건까지 배낭에 넣을 수 있을 때, 배낭의 최대 무게에 따른 최대 가치의 합은 다음과 같다.

* A의 무게 : 6 / 가치 : 13

* B의 무게 : 4 / 가치 : 8

* C의 무게 : 3 / 가치 : 6

* D의 무게 : 5 / 가치 : 12

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

 

위의 과정을 통해 우리는 다음과 같이 생각할 수 있다.

 

dp[i][j]에는 둘 중 큰 값이 저장된다.

1. dp[i-1][j]

2. i번째 물건의 가치 + dp[i][j - i번째 물건의 무게]

 

만약 i번째 물건의 무게가 j를 넘어간다면 바로 이전 값, dp[i-1][j]를 저장하면 되는 것이다.

 

---

따라서 점화식은 다음과 같이 작성할 수 있다.

 

V[i] : i번째 물건의 가치

W[i] : i번째 물건의 무게

if W[i - 1] <= j:
    dp[i][j] = max(dp[i - 1][j], V[i - 1] + dp[i - 1][j - W[i - 1]])
else:
    dp[i][j] = dp[i - 1][j]

 

 

3. 초기값 정하기

배열 dp의 값을 전부 0으로 초기화하였다면 다른 초기값은 따로 정할 필요가 없다.

 

구현 (Python)

---

import sys

N, K = map(int, sys.stdin.readline().split())  # 물품의 수, 버틸 수 있는 무게

W = []  # 각 물건의 무게
V = []  # 각 물건의 가치
for _ in range(N):
    w, v = map(int, sys.stdin.readline().split())
    W.append(w)
    V.append(v)

dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, K + 1):
        if W[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], V[i - 1] + dp[i - 1][j - W[i - 1]])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N][K])