[백준/12865] 평범한 배낭 (KnapSack 문제)

1. 문제

 

 

2. 접근 방법

'알고리즘' 하면 빠질 수 없는 문제,

'다이나믹 프로그래밍' 하면 빠질 수 없는 문제!

그 유명한 배낭 문제 (Knapsack Problem) 되시겠다.

 

나는 이 문제를 처음 접했을 때, 그러니까 대학교 3학년 시절에는 당연하게도

모든 경우의 수를 대입하는 무식한 방법을 택할 수 밖에 없었다.

그도 그럴 것이, 당시에는 DP의 개념도 몰랐었을 뿐더러 마땅한 해결책이 떠오르지 않았기 때문이다.

이렇게 문제를 풀었을 때는 각 물건 당 넣을지 안넣을지의 경우가 가능하므로,

O(2^n) 이라는 어마어마한 시간 복잡도가 나오게 된다.

만약 물건이 100개라면 2의 100승이니까... 얼마나 무자비한 계산인지는 상상에 맡기겠다.

 

자! 그렇다면 본격적으로 다이나믹 프로그래밍의 개념을 적용해보겠다.

 

다음과 같은 예시를 생각해보자.

가방의 최대 무게는 7 이고, 고를 수 있는 물건은 다음과 같이 4가지이다.

 

또한, 문제를 풀기 위해서 다음과 같은 2차원 배열을 생각해보자.

행(row)의 의미는 i번째 물건까지 담는 경우를 말하는 것이고,

열(col)의 의미는 가방의 최대 무게가 j일 때의 경우를 말하는 것이라고 가정하겠다.

 

즉, 위의 배열에서,

0번째 행은 아무것도 물건을 고르지 않은 상황이므로 모든 열의 값이 0이다.

1번째 행은 무게 6, 가치 13의 물건을 고르는 상황이므로, 최대 무게가 6이 넘는 상황에서 13의 가치를 갖는다.

 

여기에서 알 수 있듯이,

i 번째 행에서 가능한 최대 무게가 j 이고, i 번째 물건의 무게가 j 보다 작거나 같다면,

그 값이 가능한 경우 중 첫 번째 후보는 'i 번째 물건이 가지는 가치' 가 될 수 있다.

 

계속 해보자. 그렇다면 2번째 행은 어떻게 될까?

 

2번째 행은 1번 아이템과 2번 아이템을 선택할 수 있는 경우를 말한다.

여기에서는 가방의 최대 무게가 4와 5일 때 2번 물건을 선택할 수 있으므로 최대 가치로 8을 갖게 된다.

 

이제 3번째 행을 보자.

 

3번 물건을 선택할 수 있게 되었으므로, 최대 무게가 3일 때, 3번 물건의 가치인 6을 갖게 되었다.

여기에서 중요한 것은, 최대 무게가 7일 때, 14의 가치를 가지는 선택을 할 수 있게 됐다는 것이다.

이는 2번 물건과 3번 물건을 선택한 경우이다.

이는 다이나믹 프로그래밍의 특성을 잘 보여주는 계산에 해당하는데, 어떻게 나온 것일까?

생각이 조금 필요한 부분이지만, 정리하자면 다음과 같다.

 

"3번 물건을 선택 (6의 가치) 함과 동시에, 2번 물건까지 선택이 가능한 경우에서,

현재의 가능한 무게 (7) 에서 3번 물건의 무게(3) 뺀, 즉 4의 최대 무게를 가질 때의 최대 가치를 더한 값!"

 

즉, 이를 일반화시킨 문장을 다음과 같다.

 

"i 번째 물건을 선택하면서, i - 1 번째 물건을 선택하는 경우 중,

현재 가능한 최대 무게에서 i번째 물건의 무게를 뺀 값 까지의 최대 가치를 더한 값!"

 

이는 i 번째 행에서 j 의 최대 무게를 갖을 때, i 번째 물건의 무게가 j 보다 작거나 같을 때 가능한 두 번째 후보이다.

 

즉, 첫 번째 후보와 두 번째 후보를 결헙한 최종 식은 다음과 같이 생각할 수 있다.

 

만약 i번째 물건의 무게를 w[i] , i번째 물건의 가치를 v[i] ,

i번째 물건까지 선택하는 경우에서, 최대 무게가 j인 경우 dp[i][j] 라고 두고 계산한다면 다음과 같다.

 

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

else
    dp[i][j] = dp[i - 1][j];

참고로, 여기에서 최대 무게 (j) 가 i 번째 물건의 무게 (w[i]) 보다 작으면 어떻게 될까?

이럴 때는, i 번째 물건을 선택하지 않는 경우이므로, i - 1 번째 물건까지 선택하는 경우에서

해당 최대 무게일 때의 값을 가져오면 된다. 이미 해당 조건에서의 최대 가치를 가지고 있기 때문이다.

 

 

3. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, K;
int w[101] = { 0 }, v[101] = { 0 };
int dp[101][100001] = { 0 };

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

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

	cout << dp[N][K] << '\n';

	return 0;
}