[BOJ] 12865번 평범한 배낭 (C++)

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

12865번: 평범한 배낭

 

#include <iostream>
using namespace std;

int main() {
	int n, k;
	int w[101] = { 0, };
	int v[101] = { 0, };
	int dp[101][100001] = { 0, };
	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 (w[i] <= j) {
				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] << endl;
	return 0;
}

 

배낭 문제이며, 점화식은 다음과 같다.

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

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

 

예시 입력으로 만들어진 dp를 살펴보면  (물건 4개의 무게/가치가 6/13, 4/8, 3/6, 5/12)

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

 

1번 물건의 무게는 6, 가치는 13이다. 그리고 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가 답이다.