[BOJ] 백준 12865 평범한 배낭 c++ (냅색 알고리즘, Knapsack, DP)

문제 출처 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

풀이

배낭 알고리즘이라고도 불리는 Knapsack 알고리즘의 대표 문제이다.

 

여러가지 케이스가 있을때 특정 조건을 만족하는 값, 조합 등을 구하는 문제들이며 대부분 DP로 해결할 수 있다.

 

이 문제 역시 DP로 해결 할 수 있는데 문제를 요약해보면,

• 각 물건의 무게(W)와 가치(V)가 주어지고, 배낭의 용량(K)이 주어진다.
• 배낭에 넣는 물건들의 가치합의 최댓값을 구하라

이다. 예시를 통해 알아보자!

---

ex) 물건의 개수(N)는 5개, 배낭의 용량(K)은 8이라고 하고 각 물건의 정보는 다음과 같다고 하자.

 

	무게 (W)	가치 (V)
1번째 물건	1	2
2번째 물건	2	3
3번째 물건	3	4
4번째 물건	4	5
5번째 물건	5	6

 

이제 dp를 정의해야 하는데, dp[i][j]는 i번째 물건까지 봤을때, 용량이 j인 가방의 최댓값으로 정의해보자.

따라서 정답은 N번째 물건까지 봤을때, 용량이 K인 가방의 최댓값이므로, dp[N][K]일 것 이다.

 

위 예시를 dp 배열로 나타내면, 초기에는 다음과 같을 것이다.

(용량이 1인 가방에는 주어진 물건에서는 아무것도 넣지 못하므로 0, 1번째 물건만 보면 최대가 v[1]이므로 2)

 

K = 8	용량(j) 1	2	3	4	5	6	7	8
물건(i) 1	0	2	2	2	2	2	2	2
물건 2	0	_________
물건 3	0
물건 4	0
물건 5	0							정답!

 

위 dp 배열에서 파란색 부분을 구하려면 어떻게 해야 할까?

파란색 부분은 2번째 물건까지 봤을때 용량이 2인 가방의 최댓값이다.

주어진 표의 무게(w)와 가치(v)를 보면 w[1] = 1, v[1] = 2, w[2] = 2, v[2] = 3이다.

이전 물건(1번째)에서 담은 가치가 2이므로 더 이상 담을수 없다.

따라서 dp[2][2] = dp[2 - 1][2] = 2가 된다.

 

K = 8	용량(j) 1	2	3	4	5	6	7	8
물건(i) 1	0	2	2	2	2	2	2	2
물건 2	0	2
물건 3	0
물건 4	0
물건 5	0							정답!

 

이렇게 우리는 i번째 물건을 넣을 수 없는 경우, 최댓값은 dp[i - 1][j]인 것을 알 수 있다.

코드로 표현하면 아래와 같다.

if(j - w[i] < 0) dp[i][j] = dp[i-1][j];

그럼 i번째 물건을 넣을 수 있는 경우를 알아보자! 표를 좀 채우고, 빨간색 부분을 구하려면 어떻게 해야 할까?

 

K = 8	용량(j) 1	2	3	4	5	6	7	8
물건(i) 1	0	2	2	2	2	2	2	2
물건 2	0	2	3	3	5	5	5	5
물건 3	0	2	3	4	5	________
물건 4	0	2	3	4	5
물건 5	0	2	3	4	5			정답!

 

무게가 초과하지 않게 이전 물건(2번째)까지 봤을 때, 용량(j)에서 현재 물건의 무게(w[i])를 뺀 최댓값을 보자.

즉 dp[3 - 1][6 - 4]이므로 dp[2][2]가 된다.

여기에 현재 물건의 가치(v[3])를 더해주면 최댓값을 구할 수 있다.

(2번째까지 본 용량이 2인 가방의 최댓값에 3번째 물건을 넣어주는 것이다! 넣어주면 3번째, 용량 6인 최댓값이 되겠죠?)

 

정리하면, i-1번째 물건까지 보고 용량이 j-w[i]인 상황에서, i번째 물건을 넣은 상황이다.

 

이 값을 물건을 넣지 않았을때의 최댓값(dp[2][6])과 비교해서 더 큰값이 dp[3][6]의 값이 되는 것이다.

(i번째 물건을 넣지 않았을때와 넣었을때를 비교한 것이라고 생각하면 된다!)

 

K = 8	용량(j) 1	2	3	4	5	6	7	8
물건(i) 1	0	2	2	2	2	2	2	2
물건 2	0	2	3	3	5	5	5	5
물건 3	0	2	3	4	5	2 + 4
물건 4	0	2	3	4	5
물건 5	0	2	3	4	5			정답!

 

코드로 정리하면 다음과 같다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);

---

1차원 배열로 더 호율성을 높일 수도 있다고 한다. 아래 코드는 2차원 코드이다.

#include <iostream>
#include <algorithm>

using namespace std;

int w[100 + 1];
int v[100 + 1];

int dp[100 + 1][100000 + 1]; // dp[i][j] = i번째 물건까지 봤을때 용량이 j인 가방의 최댓값

int main(){	
	ios::sync_with_stdio(false); cin.tie(NULL);

	int N, K;
	cin >> N >> K; // dp[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) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
		}
	}

	cout << dp[N][K];	

	return 0;
}