[C++] 동적 계획법, 냅색

동적 계획법 (dynamic programming) 이란 무엇일까?

바로 현재 값을 구할 때, 과거에 구한 값을 활용하는 알고리즘이다.

 

예를 들어 내가 한 노드에 있는데 이 노드로 올 수 있는 길은 두 갈래 라고 하자.

왼쪽 노드에서 와야 최단 경로인지, 오른쪽 노드에서 와야 최단 경로인지 구해야한다.

출발지에서 왼쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 3의 비용으로 왼쪽 노드까지 갈 수 있다.

그리고 출발지에서 오른쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 4의 비용으로 오른쪽 노드까지 갈 수 있다.

 

그리고 왼쪽 노드의 dp 값 + 왼쪽 노드에서 도착지까지 올 때의 비용 = 3 + 10 = 13 ,

오른쪽 노드의 dp + 오른쪽 노드에서 도착지까지 올 때의 비용 = 4 + 8 = 12

... 을 계산해서 더 적은 비용을 dp 값에 갱신해주면 최단 경로를 구할 수 있다.

최단 경로는 12가 되고, 도착 노드의 dp 값은 12가 된다.

 

왼쪽 노드까지 가는 최단 경로, 오른쪽 노드까지 가는 최단 경로도 이런식으로 dp를 이용해 구한다면

원하는 지점까지의 최단 경로를 구할 수 있다.

 

---

냅색 문제를 알아보자. 냅색 문제에서는, 들 수 있는 배낭의 최대 무게가 주어진다.

그리고 물건의 무게와 물건의 최대 가치가 주어지는데, 배낭에 넣을 수 있는 물건의 최대 가치값을 구하는 문제이다.

 

동적 계획법을 이용해 냅색 문제를 해결해보자.
우선 dp의 인덱스를 무게로 나타내자

예를 들어 배낭에 넣을 수 있는 최대 무게가 7Kg 이라고 하자.
그리고 넣을 물건 3kg 짜리가 있다고 하자.
이 물건을 넣을 수도, 안 넣을 수도 있다.
넣는다고 했을 때, 7-3 = 4kg 이므로,
4kg인 배낭의 dp값 (4kg에서 담을 수 있는 최대 가치 값) + 현재 3kg짜리 물건의 가치값
... 을 계산해주자. 그리고 이 가치값과, 이 물건을 넣지 않았을 때의 가치값을 비교해보자.
그러다 보면 해당 무게 (7kg) 에서의 최대 가치 값을 구할 수 있다.

---

점화식은 아래와 같다.

dp[i][j] = max(dp[i-1][j-product[i].w] + product[i].v, dp[i-1][j]);

 

1, 2 중 max 값을 구하면 되는 것이다.
1. 이번 물건을 넣는 경우 = '이번 물품을 넣지 않았을 때의 무게 (= 최대 버틸 수 있는 무게 - 이번 물품의 무게를 뺀 값)' 에서의 최대 가치값 + 이번 물품의 가치값
무슨 소리냐면, 7kg 배낭에 3kg 넣으려고 하는거라면, 7-3 = 4kg 이니까, 4kg 에서의 최대 가치값 + 3 kg 물품의 가치값
= 무게는 4 + 3 = 7 kg을 담는 것이고, 가치값은 3kg 물품의 가치값을 포함한 최대 가치값이 되는 것!!
2. 이번 물건을 넣지 않는 경우 = 이번 물품을 넣지 않은, 이전 물품의 j kg에서의 가치값

 

 

 

 

 

 

[C++] 백준 알고리즘 2579 계단 오르기 (동적 계획법) (tistory.com)

[C++] 백준 알고리즘 2579 계단 오르기 (동적 계획법)

[C++] 백준 알고리즘 12865 평범한 배낭 (동적 계획법, 냅색) (tistory.com)

[C++] 백준 알고리즘 12865 평범한 배낭 (동적 계획법, 냅색)