[백준]동적 계획법1/평범한 배낭/12865 풀이 JAVA

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다.

세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

 

출력

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

 

 

풀이(JAVA)

백준 예제로 풀이해보겠다.

 

물건은 4개고 최대 무게는 7이다.

각 물건의 (무게, 가치)는 아래와 같다.

 

1 : (6, 13)

2 : (4, 8)

3 : (3, 6)

4 : (5, 12)

 

dp배열은 최대 가치를 담고있는 배열인데 자세히 살펴보면,

dp[n][weight] = v : 1번째부터 n번째 물건 중 최대 무게가 weight일 때 최대 가치가 v임을 나타낸다.

(최대 무게가 weight라는 것은, 최대치가 weight라는 것이지 무게가 꼭 weight 이어야 하는 것은 아님.)

 

먼저 위의 예제에선 무게가 가장 낮은 물건이 3이므로 최대 무게가 2인 물건의 가치는 모두 0이다.

(dp[1~4][1~2] = 0)

n / weight	최대 무게 1	최대 무게 2	최대 무게 3	최대 무게 4	최대 무게 5	최대 무게 6	최대 무게 7
1 : (6, 13)	0	0
2 : (4, 8)	0	0
3 : (3, 6)	0	0
4 : (5, 12)	0	0

---

 

그 다음엔 최대 무게가 3인 dp를 채워보자.(dp[1~4][3]을 채워보자)

1번째와 2번째 물건들은 무게가 각각 6, 4이므로 가치는 0이 된다.

(dp[1][3] = 0, dp[2][3] = 0)

n / weight	최대 무게 1	최대 무게 2	최대 무게 3	최대 무게 4	최대 무게 5	최대 무게 6	최대 무게 7
1 : (6, 13)	0	0	0
2 : (4, 8)	0	0	0
3 : (3, 6)	0	0
4 : (5, 12)	0	0

 

3번째 물건까지 탐색할 때, 무게가 3인 물건이 있으니 그 물건의 가치로 표를 채운다.

(dp[3][3] = 6)

n / weight	최대 무게 1	최대 무게 2	최대 무게 3	최대 무게 4	최대 무게 5	최대 무게 6	최대 무게 7
1 : (6, 13)	0	0	0
2 : (4, 8)	0	0	0
3 : (3, 6)	0	0	6
4 : (5, 12)	0	0

 

4번째 물건까지 탐색할 때, 무게가 3 이하인 물건은 3번째 물건 뿐이니 그 물건의 가치를 그대로 가져온다.

n / weight	최대 무게 1	최대 무게 2	최대 무게 3	최대 무게 4	최대 무게 5	최대 무게 6	최대 무게 7
1 : (6, 13)	0	0	0
2 : (4, 8)	0	0	0
3 : (3, 6)	0	0	6
4 : (5, 12)	0	0	6

---

이제 최대 무게가 4인 dp를 채워보자.

 

1번째 물건만 탐색할 때(dp[1][4])는... 1번째 물건의 무게가 최대 무게인 4를 넘어서 0이 저장된다.

(이전 물건의 최대 가치를 저장하면 되는데 이전 물건은 0번째 물건이고 그런 물건은 없으므로 0.)

(dp[1][4] = dp[0][4] = 0)

n / weight	최대 무게 1	최대 무게 2	최대 무게 3	최대 무게 4	최대 무게 5	최대 무게 6	최대 무게 7
1 : (6, 13)	0	0	0	0
2 : (4, 8)	0	0	0
3 : (3, 6)	0	0	6
4 : (5, 12)	0	0	6

 

선택의 폭을 2번째 물건까지로 넓히면...(dp[2][4])

마침 2번째 물건의 무게가 4이니

2번째 물건을 포함하지 않은 최대 가치(0)과 2번째 물건을 포함한 최대 가치(8)을 비교하여 배열을 채워준다.

(dp[3][4] = Math.max(dp[2][3], dp[2][0] + V[3]) = 8)

(dp[2][0]에서 0은 [최대 무게 - 현재 무게]인데, 최대 무게 - 현재 무게 = 남은 무게이다.

만약 남은 무게가 있다면 물건을 더 채워서 최대 가치를 높일 수 있다. 지금은 남은 무게가 0이라 다른 물건을 더 넣지 못한다.)

n / weight	최대 무게 1	최대 무게 2	최대 무게 3	최대 무게 4	최대 무게 5	최대 무게 6	최대 무게 7
1 : (6, 13)	0	0	0	0
2 : (4, 8)	0	0	0	8
3 : (3, 6)	0	0	6
4 : (5, 12)	0	0	6

---

위와 같은 방식으로 무게 7까지 채우면 다음과 같다.

n / weight	최대 무게 1	최대 무게 2	최대 무게 3	최대 무게 4	최대 무게 5	최대 무게 6	최대 무게 7
1 : (6, 13)	0	0	0	0	0	13	13
2 : (4, 8)	0	0	0	8	8	13	13
3 : (3, 6)	0	0	6	8	8	13	14
4 : (5, 12)	0	0	6	8	12	13	14

 

최대 무게는 7이고 1부터 4번째지의 무게를 모두 고려한 최대 가치는 dp[4][7]이므로 이를 출력하면 된다.

---

어떻게 코딩하는 것보다 설명하는 게 더 어렵지...?

할 말 있으면 코딩으로 하라는 게... 유머가 아니라 참말이라는 것을 알아냈다.(???

 

암튼 동적 계획법1의 마지막 문제~~^^

메모이제이션 문제 재밌었다. 재귀랑 좀 더 친해질 수 있었다.