[알고리즘] 배낭 문제(Knapsack Problem) 접근해보기

[위키피디아]

 

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

배낭 문제 - 위키백과, 우리 모두의 백과사전

 

 

[배낭 문제란]

 

배낭 문제는 Dynamic Programming에 있어 가장 대표적인 문제 중 하나입니다. 문제의 핵심은 최대 무게가 정해져 있는 배낭에 대해 여러 종류의 무게와 가치를 지닌 물건들을 배낭에 넣을 경우, 가장 가치 합이 높은 경우의 수(조합)를 찾아내는 것입니다.

 

 

[예제를 통해 문제 접근해보기]

 

백준의 [12865번 - 평범한 배낭] 문제를 통해 배낭 문제 알고리즘 풀이를 알아보도록 하겠습니다.

https://www.acmicpc.net/problem/12865

 

예제의 입력은 다음과 같이 주어집니다.

 

주어진 네 종류의 물건에 대해, 7kg 내에서 최대 가치합을 만들어내야 하는데, 해당 문제에서는 DFS를 활용하면 시간 초과가 발생합니다. 따라서 DP를 활용해야하는데 이를 위한 접근 방식은 다음과 같습니다.

 

테이블은 어떤 식으로 물건을 넣어야지 최대 가치합이 발생하는지 판별하기 위한 테이블입니다. 행은 순서대로 1번부터 4번까지 있으며 다음과 같은 의미를 가지고 있습니다.

 

- 1번 : 1번 물건만 고려한 경우

- 2번 : 1번, 2번 물건을 고려한 경우

- 3번 : 1번, 2번, 3번 물건을 고려한 경우

- 4번 : 1번, 2번, 3번, 4번 물건을 고려한 경우

 

 

> 1번 물건만 고려한 경우

 

1번 물건만 넣을 수 있는 경우를 고려하면, 무게가 6이기 때문에 제한이 6 이상일 때 넣을 수 있게 됩니다. 따라서 Limit 6과 7에 1번 물건의 가치인 13을 기록해줍니다.

 

> 1번, 2번 물건을 고려한 경우

 

여기서부터는 1번, 2번 물건 두 개가 주어진 상황입니다. 두 물건 모두 무게가 4 이상이기 때문에, Limit 3까지는 넣을 수 없어 0으로 기록해줍니다. Limit 4부터는 2번 물건을 넣을 수 있게 됩니다. Limit 4와 5까지 2번 물건의 가치인 8을 기록해줍니다. 

 

Limit 5부터는 경우의 수가 생깁니다. 바로 1번 물건도 넣을 수 있게 되기 때문입니다. 이 경우에는 당연히 가치가 더 높은 1번 물건을 넣어주는게 좋기 때문에 Limit 6부터 1번 무게의 가치인 13을 기록해줍니다.

 

> 1번, 2번, 3번 물건을 고려한 경우

 

이제 3번 물건까지 넣을 경우를 고려해야 합니다. 3번 물건은 무게 3에 가치 6을 갖습니다. 따라서 Limit 3 이상으로 6을 기록해줍니다. 이후 Limit 4에서는 2번 물건도 담을 수 있게 됩니다. 이 경우에는 3번 물건보다 2번 물건이 가치가 더 높기 때문에 8을 기록해줍니다. 

 

이런 식으로 Limit 5는 또 2번 물건, Limit 6번은 1번이 가치가 제일 높아 13을 기록해주지만, Limit 7에서 한 가지 경우의 수가 또 발생합니다. 바로 무게 6짜리인 1번 물건 하나를 넣는 것보다, 무게 4와 무게 3을 갖는 2번, 3번 물건의 가치 합이 14로 더 크기 때문입니다. 따라서 1번 물건의 가치를 지워주고 2, 3번 물건을 넣은 경우의 가치인 14를 기록해줍니다.

 

> 1번, 2번, 3번, 4번 물건을 고려한 경우

 

4번 물건까지 고려할 경우, 기존의 방식대로 기록하면 Limit 3은 3번 물건만, Limit 4는 2번 물건만 넣지만 Limit 5의 경우 새로 넣을 수 있는 4번 물건(무게5, 가치 12)을 넣는 경우가 가치합이 가장 큽니다. 이를 위해 Limit 5는 4번 물건의 가치를 기록해줍니다.

 

다음으로 Limit 6은 동일하게 1번 물건의 가치를 기록하고, Limit 7은 14를 기록해줍니다. 문제는 이런 식으로 값을 기록하여 마지막에 기록된 값인 14를 리턴해주면 됩니다.

 

 

[점화식 세워보기 / 풀이]

 

위의 테이블을 직접 채우는 과정을 봤다면, 어느정도 일반화된 점화식이 보일 것입니다. 물건을 i번째까지 고려했을 때, 배낭의 허용 무게가 j일 경우 얻을 수 있는 최대 가치를 DP[i][j]라고 정의하겠습니다. 이때 두 가지 경우의 수를 나눌 수 있습니다.

 

1. i번째 물건을 넣지 않는 경우

: 이때 최대 가치는 이전까지 고려한 상태와 동일함

DP[i - 1][j]

 

2. i번째 물건을 넣는 경우

: 하지만 i번째 물건의 무게가 현재 허용 무게 j이하일 경우에만 가능함, 이 경우의 가치는 i번째 물건의 가치 + (남은 무게에서 얻을 수 있는 최대 가치)가 됨

DP[i - 1][j - Weight] + Value

 

> 여기서 DP[i - 1][j - Weight]라는 식은 현재 i번째 물건을 넣었을 때, 남는 무게 공간을 뜻합니다(이 상태에서의 최대 가치는 DP[i - 1][j]). 이 가치와 현재 선택해서 넣은 물건의 가치를 넣어줍니다.

 

이를 점화식으로 표현하면 다음과 같습니다.

 

즉, 칸을 채워 넣는 과정은 "현재 물건을 넣느냐, 안 넣느냐"의 두 경우를 비교하여 더 큰 값을 선택하는 과정입니다. 이를 코드로 표현하면 다음과 같습니다.

// 백준 12865 평범한 배낭
// 골드5
// 1 ≤ N ≤ 1,000,000(10^6)

#include <iostream>
#include <vector>
using namespace std;

// N개의 물건이 W무게와 V가치를 가짐
// 최대 K만큼의 무게 제한에 대해, V(가치) 합을 최대로 만들기
struct Goods
{
	int Weight = 0;
	int Value = 0;
};

int main()
{
	int N, K;
	cin >> N >> K; // N : 물건 갯수, K : 최대 무게 제한

	vector<Goods> GoodsTable(N, { 0, 0 });
	for (int i = 0; i < N; i++)
	{
		cin >> GoodsTable[i].Weight >> GoodsTable[i].Value;
	}

	int DP[101][100001];

	for (int i = 1; i <= N; i++) 
	{
		for (int j = 1; j <= K; j++) 
		{
			int CurWeight = GoodsTable[i - 1].Weight;
			int CurValue = GoodsTable[i - 1].Value;

			// 검토 과정
			if (CurWeight <= j) // 현재의 짐을 담을 수 있음
			{
				// 1. 현재 짐을 넣지 않는 경우, 바로 윗 칸의 값 // DP[i - 1][j]
				// 2. 현재 짐을 넣는다. // DP[i - 1][j - CurWeight] + CurValue
				DP[i][j] = max(DP[i - 1][j - CurWeight] + CurValue, DP[i - 1][j]);
			}
			else // 현재의 짐을 담을 수 없음
			{
				// 바로 윗 칸의 값 // DP[i - 1][j]
				DP[i][j] = DP[i - 1][j];
			}
		}
	}

	cout << DP[N][K];

	return 0;
}