[C/C++] 백준 12865번 - 평범한 배낭 (DP, Knapsack 알고리즘)

 

 

<코드>

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

int N, K;
int DP[101][100001];
int W[101];
int V[101];

// 점화식 max(DP[i-1][j], DP[i-1][j-W[i]])

int main()
{
	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) DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);
			 else DP[i][j] = DP[i - 1][j];
		}
	}

	cout << DP[N][K];

}

 

배낭 문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭 문제를 분할 가능 배낭 문제(Fractional), 짐을 쪼갤 수 없는 경우의 배낭 문제를 0-1 배낭 문제(0-1 Knapsack)라 부른다. - 위키백과

따라서 해당 문제는 0-1 Knapsack Problem이며, 점화식은 아래와 같다.

DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);

여기서 i는 배낭에 넣을 물건 번호, j는 현재 배낭의 무게를 의미합니다.

 

위의 예제입력으로 만들어진 dp값을 살펴보면 아래와 같습니다.

dp[i][j]	[ ][1]	[ ][2]	[ ][3]	[ ][4]	[ ][5]	[ ][6]	[ ][7]
[1][ ]	0	0	0	0	0	13	13
[2][ ]	0	0	0	8	8	13	13
[3][ ]	0	0	6	8	8	13	14
[4][ ]	0	0	6	8	12	13	14

첫번째 물건의 무게는 6 그리고 가치는 13입니다. 편의상 1번 물건이라고 하겠습니다. 그리고 j는 1에서 7까지 변하는데 j가 늘어날수록 가방의 크기가 커진다고 생각해봅시다. 1번 물건을 넣어야 할 때 가방의 크기가 6 즉, j=6일때 비로소 1번 물건을 넣을 수 있고 dp[1][6]은 13으로 업데이트됩니다. 그리고 dp[1][7]일때 dp[1][7-(1번 물건의 무게)] = dp[1][1]은 0이므로 다음 i는 2로 넘어갑니다.

2번 물건의 무게는 4, 가치는 8입니다. j가 늘어나면서 가방의 크기가 4가 되었을 때 2번 물건을 넣을 수 있고 dp[2][4]의 값은 0이었으므로 2번 물건의 가치인 8로 업데이트해줍니다. 그리고 가방 크기가 6이 되었을 때 2번 물건을 넣어놓은 것보다 1번 물건을 넣어놓은 것이 가치가 더 크므로 dp[2][6]은 13입니다. 

이런 식으로 dp값을 구해주는데 이 중에서 dp[3][7]를 살펴보면

dp[3][7]은 dp[2][7]과  dp[3][7-(3번 물건의 무게)] + v[3]  둘 중 큰 값을 저장하게 됩니다. dp[3][4]값은 6이고 v[3]은 8이므로 최종적으로 dp[2][7]은 13, dp[3][7]은 14이므로 dp[3][7]에는 14가 저장됩니다.

그렇게 하여 1번부터 N번 물건까지 모두 넣어봤을 때 가치합이 가장 큰 값 = dp[N][K]는 2, 3번 물건을 넣은 14가 답이게 됩니다.

 

 

 

 

 

www.acmicpc.net/problem/12865

12865번: 평범한 배낭