(c++) 백준 12865 평범한 배낭

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

12865번: 평범한 배낭

---

나의 풀이

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, C;
int K[200][100002] = { 0 };

int main() {
	cin >> N >> C;
	for (int i = 1; i <= N; i++) {
		int W, V;
		cin >> W >> V;
		for (int k = 1; k <= C; k++) {
			if (W > k) {
				K[i][k] = K[i - 1][k];
			}
			else {
				K[i][k] = max(K[i - 1][k], K[i - 1][k - W] + V);
			}
		}
	}
	cout << K[N][C] << endl;
}

---

해당 알고리즘의 원리는 k의 용량일 때 가장 높은 가치를 가지는 경우를 구하는 것이다.

 

else에서 max(K[i - 1][k], K[i - 1][k - W] + V)를 하는 이유는 

기존 배낭에서 i번째 물건 만큼 용량을 제외하고 i번째 물건을 추가하였을 경우와

기존 배낭의 경우의 가치를 비교하기 위해서이다.

 

기존 예시를 활용해서 풀이를 해보자

 

예시의 입력 : 

4 7
6 13
4 8
3 6
5 12

 

i = 0일 때

세로는 각 물건을 의미한다. ex) i = 1 : 6 / 13, i = 2 : 4 / 8

가로는 배낭이 수용 가능한 용량(무게)을 의미한다.

	k=0	k=1	k=2	k=3	k=4	k=5	k=6	k = 7
i = 0	0	0	0	0	0	0	0	0
i = 1	0
i = 2	0
i = 3	0
i = 4	0

i = 1일 때,

k < 6일때까지는 if문에 해당하여 K[i][k] = K[i-1][k]여서 0이 되고

k = 6일때부터는 else에 해당하여  max(K[i - 1][k], K[i - 1][k - W] + V);를 수행한다.

k = 6이면 max(0,0+13)이고 k = 7이면 max(0,0+13)이다.

w	v		k=0	k=1	k=2	k=3	k=4	k=5	k=6	k=7
		i=0	0	0	0	0	0	0	0	0
6	13	i=1	0	0	0	0	0	0	13	13
4	8	i=2	0
3	6	i=3	0
5	12	i=4	0

i = 2일때,

k < 4 이면 if문에 해당하여 0이 되고

k = 5,6이면 max(0,0+8) / k = 6,7이면 max(13,0+8)이다.

w	v		k=0	k=1	k=2	k=3	k=4	k=5	k=6	k=7
		i=0	0	0	0	0	0	0	0	0
6	13	i=1	0	0	0	0	0	0	13	13
4	8	i=2	0	0	0	0	8	8	13	13
3	6	i=3	0
5	12	i=4	0

i = 3일때,

k < 3 이면 if문에 해당하여 0이 되고

k = 3이면 max(0,0+6) / k = 4,5이면 max(8,0+6) / k = 6이면 max(13,0+6) / k = 7이면 max(13,8+6)이다.

w	v		k=0	k=1	k=2	k=3	k=4	k=5	k=6	k=7
		i=0	0	0	0	0	0	0	0	0
6	13	i=1	0	0	0	0	0	0	13	13
4	8	i=2	0	0	0	0	8	8	13	13
3	6	i=3	0	0	0	6	8	8	13	14
5	12	i=4	0

i = 4일때,

k < 5 이면 if문에 해당하고

k = 5이면 max(8,0+12) / k = 6이면 max(13,0+12) / k = 7이면 max(14,0+12)이다.

w	v		k=0	k=1	k=2	k=3	k=4	k=5	k=6	k=7
		i=0	0	0	0	0	0	0	0	0
6	13	i=1	0	0	0	0	0	0	13	13
4	8	i=2	0	0	0	0	8	8	13	13
3	6	i=3	0	0	0	6	8	8	13	14
5	12	i=4	0	0	0	6	8	12	13	14

해서 답은 14이다.

 

 

역시 DP(Dynamic Programming)는 너무 어려운 것 같다..

확실한 풀이법이 있으나 이를 이해하는데 조금 시간이 걸리는 편이다.