[C++] 백준 12865번 : 평범한 배낭

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

12865번: 평범한 배낭

---

문제 풀이

 배열 DP[i][j]는 가방이 j 무게 일 때 i 번째 물건까지 확인했을 때의 최대 가치이다.

예를 들어서 DP[3][5]는 무게 5인 가방에 대해서 3번째 물건까지 확인했을 때의 최대가치이다.

경우는 단순하게 2가지로 i번째 물건을 담았을 때와 담지 않았을 때로 나뉜다.

표를 통해서 이해하면 매우 쉽다. (문제 참고!)

	0	1	2	3	4
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	8
5	0	0	8	8	12
6	0	13	13	13	13
7	0	13	13	14	14

가로는 가방의 무게를 나타내고, 세로는 i 번째 물건이다. 가장 중요한 점화식은

i번째 물건을 담을 때 : DP[i][j] = i번째 물건의 가치 + DP[i-1][j - i번째 물건의 무게]와 DP[i-1][j] 중 최댓값

i번째 물건을 담지 않을 때 : DP[i][j] = DP[i-1][j]

여기서 DP[i-1][j - i번째 물건의 무게] 가 가장 중요하다. 표에서 강조한 부분을 보면 바로 이해할 수 있다.

무게가 7인 배낭을 만들 때 무게가 3과 4인 물건을 넣을 수도 있고 그냥 무게가 6인 물건만 넣을 수 있다.

여기서 max함수를 통해서 가치가 최대인 값을 비교해서 대입하는데 DP[i-1][j - i번째 물건의 무게] 이 점화식이 무게가  3인 상태에서 무게가 4인 물건을 추가로 집어넣을 때를 의미한다!

느낀 점

다이나믹 프로그래밍1의 마지막 문제인데 접근을 아직도 어려워한 거 같아서 약간 좌절한 문제였다. 따로 익숙해질 시간이 필요한 문제인 것 같다.

코드

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

int n, k;
int DP[101][100001];
int w[101];
int v[101];

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++) {
			DP[i][j] = DP[i - 1][j];
			if (j - w[i] >= 0) 
				DP[i][j] = max(DP[i - 1][j], v[i] + DP[i - 1][j-w[i]]);
		}
	}
	cout << DP[n][k];
}