동적계획법과 냅색(Knapsack) 문제
- 짐 싸기 문제(Knapsack)는 동적 계획법으로 풀 수 있는 경우가 많습니다.
- 여러 물건이 있을 때, 특정한 조건을 만족하는 조합을 구하는 문제입니다.
- 백준 온라인 저지의 12865번 : 평범한 배낭 https://www.acmicpc.net/problem/12865 문제를 토대로 살펴보겠습니다.
- 물건의 무게와 가치가 주어지고, 담을 수 있는 배낭의 최대 용량이 주어진다고 가정합니다.
- 이 때, 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 구하려고 합니다.
예 : 물건의 수가 N=4개이고, 배낭의 최대 용량이 K=7이라고 할 때, 다음과 같이 물건의 정보가 주어졌습니다.
| 1번 물건 | 2번 물건 | 3번 물건 | 4번 물건 | |
|---|---|---|---|---|
| W(무게) | 6 | 4 | 3 | 5 |
| V(가치) | 13 | 8 | 6 | 12 |
그리고 dp[i][j]를 다음과 같이 정의합니다.
dp[i][j]= 처음부터 i번째까지의 물건을 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어간 물건의 가치합의 최댓값
따라서, 이 문제의 정답은 dp[N][K]에 들어 있을 것입니다.
그 이유는, 1부터 N개의 모든 물건들을 살펴보고, 배낭 용량이 K였을 때 이 배낭에 들어가 있는 물건들의 가치합의 최댓값이 들어가게 될 것이기 때문입니다.
이제 dp[i][j]의 점화식을 나타낼 수 있습니다. 이 문제는 dp[i][j]의 값을 차례대로 채워나가야 합니다.
dp[i][j]에는, dp[i-1][j] 의 값과 dp[i-1][j-w[i]]+v[i]의 값 중 더 큰 값이 들어가게 됩니다.
이것의 의미는 다음과 같습니다.
i번째 물건의 무게는
w[i]이고, 가치는v[i]입니다.- 이제 이 i번째 물건을 배낭에 넣어보려고 합니다. 이 때 배낭의 용량은 j 입니다.
- 용량이 j인 배낭에 i번째 물건을 넣지 않았을 때의 가치합의 최댓값은
dp[i-1][j]입니다. 다시 말해,dp[i-1][j]의 값은 배낭의 용량이 j 였고 i-1번째 물건까지 살펴봤을 때의 가치합의 최댓값입니다. - 용량이 j인 배낭에 i번째 물건을 넣었을 때의 상황은
dp[i-1][j-w[i]]+v[i]가 됩니다.- 즉, i-1번째 물건까지 살펴보았고 배낭의 용량이 j-w[i] 였을 때의 값에, 새롭게 i번째 물건을 넣은 상황이 됩니다.
예를 들어,
dp[3][6]의 값을 구하는 상황일 때를 가정해 보겠습니다.- 용량이 6인 배낭에 i=3번째 물건을 넣지 않았을 때의 최댓값은
dp[2][6]에 저장되어 있습니다. - 용량이 6인 배낭에 i=3번째 물건을 넣을 때의 값은
dp[2][6-w[3]]+v[3]=dp[2][3]+v[3]입니다.- 즉, 최대 가치합으로 물건이 들어가 있는 용량이 3인 배낭에, i=3번째 물건(무게가 3)을 새롭게 넣는 상황이 됩니다. dp에 저장되는 값은 가치의 합이므로 v[3] 을 더해준 것입니다.
냅색 문제는 쉽게 말해서, i번째 물건을 넣었을 때와 넣지 않았을 때, 둘 중 더 가치가 큰 것을 가져오면 되는 것입니다!
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
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int w[101]; // 무게
int v[101]; // 가치
int dp[101][100001];
int N, K; // 물품의 수 N, 준서가 버틸 수 있는 무게 K
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
if (j - w[i] >= 0) { // i번째 물건을 넣을 수 있다면?
dp[i][j] = max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i]);
// 넣지 않을 때와 넣었을 때, 둘 중 더 큰 것으로 초기화
}
else{ // i번째 물건을 넣을 수 없다면, 배낭 용량은 같고 넣지 않았을 때의 값으로 초기화
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[N][K];
return 0;
}
그런데 위 코드를 좀 더 최적화 할 수 있습니다. dp를 2차원 배열을 사용하지 않고, 1차원 배열로 해결할 수 있는 것입니다.
단, 위의 2차원 배열 코드는 가방 용량을 1부터 K까지 작은 쪽부터 큰 쪽까지 순서대로 살펴보았다면,
1차원 dp 배열을 사용할 때에는 가방 용량을 K부터 1까지 큰 쪽에서 작은 쪽의 순서로 살펴보아야 합니다.
초기 dp 배열의 값은 모두 0으로 초기화되어 있으며, 최대 K 용량의 배낭일 때부터 1일 때까지 차례대로 살펴봅니다. 이 배열에도 위와 똑같이 배낭 용량이 K일 때, 들어간 물건들의 최대 가치합이 들어가게 됩니다.
1번 물건부터 넣기를 시도해 봅니다. (아래 표는 dp 1차원 배열의 값입니다.)
- 배낭 용량이 7일 때, 1번째 물건을 넣어볼 수 있으며, 가치는 0 < 13 이므로 13을 넣습니다.
- dp[7] = 0
- dp[7-w[1]] + v[1] = dp[1] + v[1] = 0 + 13 = 13
- 배낭 용량이 6일 때, 1번째 물건을 넣어볼 수 있으며, 가치는 0 < 13 이므로 13을 넣습니다.
- dp[6] = 0
- dp[6-w[1]] + v[1] = dp[0] + v[1] = 0 + 13 = 13
- ….
K = 1까지의 모든 용량을 살펴보고 채워진 dp 배열은 다음과 같아집니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 13 | 13 |
이제 2번 물건을 넣기 시도해 봅니다.
- 배낭 용량이 7일 때, 2번째 물건의 무게가 7보다 작으므로 넣어볼 수 있는데, dp[7-w[2]] + v[2] = dp[3]+v[2] 의 값보다 dp[7]의 값이 더 크므로 값은 변하지 않습니다.
- 즉, 배낭 용량이 3이었을 때 들어 있는 최대 가치합 상황(dp[3])에, 무게가 4인 2번째 물건을 넣었을 때 모든 무게의 가치합 8 (dp[3]+v[2] = 0 + 8 = 8) 보다, 배낭 용량이 7이었을 때 들어 있던 물건들의 최대 가치합(dp[7])인 13이 더 큰 상황이라, 2번째 물건을 넣지 않았습니다.
- …
K = 1까지의 모든 용량을 살펴보고 채워진 dp 배열은 다음과 같아집니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 8 | 8 | 13 | 13 |
이제 3번 물건을 넣기 시도해 봅니다.
- 배낭 용량이 7일 때, 3번째 물건의 무게가 7보다 작으므로(3) 넣어볼 수 있는데, dp[7-w[3]]+v[3] = dp[4]+v[3] 의 값인 8+6 = 14보다 dp[7]의 값이 더 작으므로, dp[7]의 값을 14로 업데이트 합니다.
- 즉, 배낭 용량이 4였을 때 들어 있는 최대 가치합 상황(dp[4])에, 무게가 3인 3번째 물건을 넣었을 때 모든 무게의 가치합은 14 (dp[4]+v[3] = 8 + 6 = 14) 입니다. 그리고 기존에 배낭 용량이 7이었을 때 들어 있던 물건들의 최대 가치합은 13이었습니다.
- 따라서, 2번 물건(무게 4, 가치 8) 과 3번 물건(무게 3, 가치 6)을 넣었을 때가, 1번 물건(무게 6, 가치 13) 만을 넣었을 때보다 그 가치가 더 크므로, 업데이트 되는 것입니다.
- …
K = 1까지의 모든 용량을 살펴보고 채워진 dp 배열은 다음과 같아집니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 0 | 0 | 6 | 8 | 8 | 13 | 14 |
4번째 물건을 넣기 시도 하는 것도 위와 같은 방식으로 진행하면 됩니다. 이 부분은 위의 설명들을 참고하여, 직접 표를 작성해 보시는 것도 도움이 되실 것 같습니다.
이렇게 차례대로 물건들을 넣는 시도를 해 봅니다. 네 번째 물건까지 모든 물건을 다 넣기 시도해본 다음, 최종적으로 구해야 하는 값은 dp[K] 에 들어가게 됩니다. 따라서 답은 dp[K]가 됩니다. 이 예시로는 14가 최종 답이 됩니다.
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
34
35
36
37
38
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int w[101]; // 무게
int v[101]; // 가치
int dp[101];
int N, K; // 물품의 수 N, 준서가 버틸 수 있는 무게 K
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= N; i++) {
for (int j = K; j >= 1; j--) {
if (w[i] <= j) { // 넣을 수 있다면?
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
// 그 물건을 넣었을 때와 넣지 않았을 때 중 더 큰 값으로 초기화
}
}
}
cout << dp[K];
return 0;
}
백준에 제출한 결과, 두 번째 방식으로 일차원 dp 배열을 사용했을 때 실행 시간이 2배 이상 더 빠름을 확인할 수 있었습니다.