[Algorithm] DP-2 동적 테이블을 작성하는 Knapsack 예제풀이이다.

[Algorithm] DP-2 동적 테이블을 작성하는 Knapsack 예제풀이이다.

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1

4 7 6 13 4 8 3 6 5 12

예제 출력 1

14

---

DP table을 그려서 푸는 문제이다.
column에는 버틸 수 있는 무게가 들어가고 row에는 특정 물건이 들어간다.
아래 표를 한 row 씩 채워 나가야 한다.
row에서는 해당 물건을 고려 했는지 안했는지 정해진다.

i/w	0	1	2	3	4	5	6	7
0	X	X	X	X	X	X	X	X
6kg/13$	X	X	X	X	X	X	X	X
4kg/8$	X	X	X	X	X	X	X	X
3kg/6$	X	X	X	X	X	X	X	X
5kg/12$	X	X	X	X	X	X	X	X

---

예를 들어 아래처럼 4kg/8$ 행의 표를 채웠을 경우 6kg와 4kg짜리를 사용하여 해당 열의 무게를 채웠을 때의 최대 값을 나타내게 된다. 분홍색으로 표시된 칸의 경우 6kg, 4kg을 조합하여 7kg 가방을 채웠을시 가치의 최대 값이 된다. (7kg 가방에 6kg가 들어있는것이 최대값이다.)

i/w	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
6kg/13$	0	0	0	0	0	0	13	13
4kg/8$	0	0	0	0	8	8	13	13

그럼 이 표는 어떤 규칙으로 채우는가 P[i][w] = { P[i-1][w] (i < w_k),
max(P[i-1],P[i-1][w-w_k]+V_k )(i >= w_k) } 위의 규칙으로 채워진다. 단, 0번째 행의 경우 채울 물건이 없는 것이므로 모든 row의 값을 0으로 채워준다. 의미를 풀어보면 배낭이 들 수 있는 무게가 현재 채우려는 row, i에 해당하는 무게 w_k 보다 작을 때는 기존에 채워 놓았던 값인 P[i-1][w]값으로 채우라는 것이다. 아래 표의 분홍색 row에 해당하는 물건은 4kg/8$이며 그 무게보다 작은, i<4인 경우는 해당값을 보라색(분홍색의 바로 위의 행)의 값을 가져온다.

i/w	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
6kg/13$	0	0	0	0	0	0	13	13
4kg/8$	0	0	0	0	X	X	X	X

---

아래 표의 분홍색 칸을 채울때는 보라색칸의 8에 3kg물체 가격 6 을 더한 14 의 값과 바로 위의 보라색 13을 비교하여 큰 값을 취한다. 의미적으로 보면

• 기존에 7kg의 배낭을 6kg/13$ , 4kg/8$ 2개의 물체가 선택 가능할 때 구해놓은 최적값(13)
• 3kg/6$의 선택지가 추가되었을 때 4kg까지만 채운 배낭의 최적값(8)에 3kg/6 $ 를 추가한 14
• 둘을 비교하여 큰값을 취해준다

i/w	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
6kg/13$	0	0	0	0	0	0	13	13
4kg/8$	0	0	0	0	8	8	13	13
3kg/6$	0	0	0	6	8	8	13	14
5kg/12$	0	0	0	6	8	12	13	14

채워주는 순서에 따라 값이 다를 것 같지만 마지막 row의 최종 결과 값은 같다.

i/w	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
5kg/12$	0	0	0	0	0	12	12	12
3kg/6$	0	0	0	6	6	12	12	12
4kg/8$	0	0	0	6	8	12	12	14
6kg/13$	0	0	0	6	8	12	13	14