[Beakjoon Online Judge] 12865 - 평범한 배낭

I 문제 소개

---

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

 

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

---

II 문제 풀이

---

이름도 내용도 상당히 평범해보이는 문제지만, 사실은 그렇지 않다.

 

문제들을 풀다보면 이 문제를 포함해서 그것이 차지하는 공간과 그것의 가치가 서로 달라 최대의 가치로 묶는 형식의 문제가 종종 보인다. 겉보기에는 그리디나 DP로 쉽게 풀 수 있을 것만 같지만, 조금만 생각해도 반례들이 툭툭 튀어나와서 생각보다 쉽게 풀리지 않는다.

 

이러한 문제를 풀 때 사용하는 알고리즘이 배낭(Knapsack) 알고리즘이다. 배낭 알고리즘은 배낭 문제(Knapsack Problem)에서 비롯된 알고리즘으로, 결과 식만 보면 굉장히 복잡하지만 원리를 알면 쉽다.

 

여기서 말하는 배낭 문제가 사실 이 문제와 동일한 문제이다. 따라서 배낭 알고리즘을 알면 이 문제를 풀 수 있다.

 

배낭 알고리즘의 기본 원리는 DP이다. 단, 캐시에 저장할 때 값은 가치합의 최대가 되겠고, 조건은 개수와 무게 두가지를 따진다. 따라서 무게 K안에 N개를 담을 때 최대 가치합인 DP[N][K]가 이 문제의 해답이 되겠다.

 

DP[N][K]를 구하기 위해서는 DP[0][0]부터 구해나가야할 것인데, 구하는 원칙은 다음과 같다.

 

(배낭에 아무 물건도 없을 경우)
1. 물건들을 무게 순(오름차순)으로 정렬한다.
   ㄴ사실 정렬을 하지 않아도 되지만, 빠른 이해를 위해 정렬을 한다고 가정하겠다.
2. 물건 하나에 대해 들 수 있는 무게인 K를 하나씩 늘려가며 이 물건이 들어갈 수 있는지 비교한다.
3. 이 물건의 무게 W와 K가 같아질 때부터 이 물건은 배낭에 들어간다. (이 때, 물건이 한 개가 들어갔으므로 N은 +1이 된다)
4. 즉, DP[1][W] = V가 된다. (V는 들어간 물건의 가치)

(배낭에 물건이 있는 경우)
5. 이전 물건이 들어가 있는 상태에서 그 다음 물건의 정보를 가져온다.
6. K를 늘려가면서 그 다음 물건의 무게와 같아지는지 비교한다. 이 때, 배낭 안에 있는 물건의 무게는 신경쓰지 않는다.
7. K가 그 다음 물건의 무게와 같아졌을 경우, 다음 두가지 경우를 비교해본다.
    i) 현재 배낭 안에 있는 물건들의 가치합이 비교하고자 하는 물건의 가치보다 높은 경우
    ii) 이 물건이 배낭 안에 있는 물건들의 가치합보다 가치가 높은 경우

7-i의 경우 이 물건은 넣을 필요가 없어져 그 다음 물건으로 넘어가면 된다.
7-ii의 경우 배낭 안에 있는 물건들을 싹 빼고 이 물건을 넣는 것이 이득이 된다.

이후 5 ~ 7을 반복한다.

 

중요한 포인트는 물건들을 무게 순으로 하나씩 탐색해보면서 지금 내 배낭에 있는 물건을 털고 얘를 담는 것이 이득인지 계산하는 것이다.

 

0. 초기 환경 설정

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int backpack[102][100002];

int main(void)
{
	int N, K, W, V;
	vector<pair<int, int>> wv;

	cin >> N >> K;
	wv.push_back({ 0,0 });

	for (int i = 0; i < N; i++)
	{
		cin >> W >> V;
		wv.push_back(make_pair(W, V));
	}
	return 0;
}

최댓값 비교를 할 것이기 때문에 max( )를 쓰기 위해 algorithm 헤더를 불렀다.

그리고 backpack이라는 이차원 배열을 만들었는데 이 배열을 캐시(DP)로 사용할 것이다.

wv라는 벡터에는 pair 형태의 값이 들어가는데, 문제에서 입력하는 물건의 무게와 가치를 저장한 벡터다.

 

1. Knapsack 알고리즘(이론)

N = 0 or K = 0

 

예제 입력

4 7
6 13
4 8
3 6
5 12

문제에서 준 예제를 갖고 풀어볼 것이다. backpack 배열을 나타내보았는데, 문제의 예제에서 N = 4, K = 7이기 때문에 임의로 이렇게 표현했다.

 

들 수 있는 무게(K)가 0이거나 물건의 개수(N)가 0이면 당연히 어떤 물건도 배낭에 넣을 수 없어 자동으로 가치합은 0이 된다. 위 사진은 그것을 나타내었다.

 

 

N = 1

물건을 한 개 담을 수 있을 때(N = 1), 들 수 있는 무게(K)를 점점 늘려가면서 최대 가치를 구해보았다.

당연하게도 들 수 있는 무게가 1이나 2일 때에는 그것보다 같거나 작은 무게의 물건이 없어 가치는 0이다.

그리고 K=6일때 무게가 6이고 가치가 13인 물건을 넣어 가치합은 13이 되고, K=7로 늘어난다고 해도 그것보다 가치가 큰 물건이 없으므로 backpack[1][7]은 여전히 13이 된다.

 

 

 

N = 2

물건을 두 개 담을 수 있을 때에는 얘기가 조금 복잡해진다.

역시 K<=2일 때에는 아무 물건도 넣을 수 없으므로 0이고, K가 6이 될 때까지에는 두 개의 물건을 넣을 수 없어 한 개의 물건을 넣었을 때(N=1)의 값이 그대로 계승된다.

그런데, backpack[2][7]에서 값이 달라진다.

backpack[1][7]에서는 backpack[1][6]의 값이 그대로 계승되었으나, backpack[2][7]에서는 무게가 3인 물건과 무게가 4인 물건을 넣을 수도 있어졌다. 따라서 backpack[1][7]과 (backpack[1][3] + backpack[1][4])값을 비교해봐야한다.

무게가 3인 물건과 4인 물건을 넣은 값(14)이 최대값이므로 backpack[2][7]의 값은 13이 아닌 14가 된다.

 

 

N = 4

이 과정을 반복해나간다면 최종적인 모습은 이렇게 될텐데, 여전히 이를 구현하려니 뭔가 복잡하다.

어떻게 보면 완전 탐색이기 때문에 시간 복잡도가 보장되지 않는다.

여기서 아이디어는 굳이 모든 물건을 한번씩 탐색해나가면서 경우의 수를 구해봐야할까? 이다.

만약 N = 1이 물건을 1개 넣는 방법이라는 광범위한 조건이 아니라, 1번째 물건을 넣는 방법이고,

N = 2가 2번째 물건을 넣을지 말지 결정하는 방법이라고 생각한다면, 중간에 값이 빈다고 해도 결국 N = 4인 행에서는 모든 물건을 한번씩 대입해봤으므로 같은 결과가 나올 것이다. 

 

이를 좀 더 식처럼 표현을 한다면,

if N번째 물건의 무게 <= K
    backpack[N][K] = max(N번째 물건의 가치 + backpack[N-1][N번째 물건의 무게를 뺀 값], backpack[N-1][K])

이 되겠다.

 

따라서 이를 다시 표로 작성해본다면

이런 형태로 작성이 될 것이다.

 

2. Knapsack 알고리즘(코드)

for (int i = 1; i < N+1; i++)
{
	for (int j = 0; j < K+1; j++)
	{
		if (i == 0 || j == 0)
			backpack[i][j] = 0;
		else if (wv[i].first <= j)
			backpack[i][j] = max(wv[i].second + backpack[i - 1][j - wv[i].first], backpack[i - 1][j]);
		else
			backpack[i][j] = backpack[i - 1][j];
	}
}

N과 물건 벡터(wv)의 인덱스를 일치시키기 위해 i를 1부터 시작하였다.

앞서 wv 벡터를 pair를 이용해 만들었는데, 첫번째 값이 무게이고 두번째 값이 가치이다.

따라서 wv[i].first가 i번째 물건의 무게가 되겠다.

 

max에서 비교하는 첫번째 값은 (이 물건의 가치 + 이전에 구해놓은 배낭에서 이 물건의 무게만큼 뺐을 때의 최대 가치합)이고, 두번째 값은 이 물건을 넣지 않는 이전에 구해놓은 값이 되겠다.

 

당연히 내가 들 수 있는 무게보다 물건의 무게가 무겁다면 같은 무게에서 이 물건을 넣지 않는 값이 그대로 계승된다.

 

3. 최종

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int backpack[102][100002];

int main(void)
{
	int N, K, W, V;
	vector<pair<int, int>> wv;
	cin >> N >> K;

	wv.push_back({ 0,0 });
	for (int i = 0; i < N; i++)
	{
		cin >> W >> V;
		wv.push_back(make_pair(W, V));
	}
	for (int i = 1; i < N+1; i++)
	{
		for (int j = 0; j < K+1; j++)
		{
			if (i == 0 || j == 0)
				backpack[i][j] = 0;
			else if (wv[i].first <= j)
				backpack[i][j] = max(wv[i].second + backpack[i - 1][j - wv[i].first], backpack[i - 1][j]);
			else
				backpack[i][j] = backpack[i - 1][j];
		}
	}
	int ans = backpack[N][K];
	cout << ans;
	
	return 0;
}

최종 코드의 모습이다.

지금 보니 배낭 알고리즘을 적용하는 부분에서 i = 1부터 시작해 backpack[0][j]인 부분이 모두 null이 되어 오류가 날 것 같은데 아마 C++에서 임의로 0으로 채운 것 같다.

 

III 느낀점

---

정확히 어떤 문제인지 언급은 할 수 없으나 SW마에스트로 12기 1차 코딩테스트에 출제된 문제 중 배낭 알고리즘으로 풀 수 있는 문제가 있었다. 그 당시에 나는 이 알고리즘을 몰라서 풀지 못했는데, 이후에 이 문제를 접하면서 이렇게 풀면 됐었구나라고 깨달았다.

 

처음 이 알고리즘을 접했을 때 점화식으로 봤는데 너무 복잡해서 이해하는데 오래걸렸다. 그런데 오히려 과정을 보니까 식이 복잡한거지 생각보다 간단했다.

 

이 알고리즘으로 풀 수 있는 문제가 생각보다 많을 것 같아서 오늘도 한단계 성장했다고 볼 수 있다!

 

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 12865번 평범한 배낭 C++

BOJ 12865번 평범한 배낭 C++

백준 12865번 평범한 배낭 C++