Posts [알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)
Post
Cancel

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)


동적계획법과 냅색(Knapsack) 문제


  • 짐 싸기 문제(Knapsack)는 동적 계획법으로 풀 수 있는 경우가 많습니다.
  • 여러 물건이 있을 때, 특정한 조건을 만족하는 조합을 구하는 문제입니다.


  • 물건의 무게와 가치가 주어지고, 담을 수 있는 배낭의 최대 용량이 주어진다고 가정합니다.
  • 이 때, 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 구하려고 합니다.

예 : 물건의 수가 N=4개이고, 배낭의 최대 용량이 K=7이라고 할 때, 다음과 같이 물건의 정보가 주어졌습니다.

 1번 물건2번 물건3번 물건4번 물건
W(무게)6435
V(가치)138612

그리고 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 배열은 다음과 같아집니다.

1234567
000001313

이제 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 배열은 다음과 같아집니다.

1234567
000881313

이제 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 배열은 다음과 같아집니다.

1234567
006881314

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배 이상 더 빠름을 확인할 수 있었습니다.


수정 내역

앞으로는 포스팅 시 몇 번씩 더 확인하여 오타가 없도록 하겠습니다.

  • 2차원 배열을 활용한 소스코드 부분의 오타 수정(if(j - w[i]) 조건문 내부 부분)

  • 1차원 배열을 활용한 풀이 설명에서 1번째 물건부터 넣을 때의 표 내용이 두번째 물건을 넣을 때의 표로 잘못 들어간 부분 수정

  • https://hevton.tistory.com/362 에서 지적해 주셨습니다. 감사합니다!