배낭 알고리즘

n개의 물건과 배낭이 있고, 물겅에는 가치와 무게 값이 존재한다. 

배낭에는 최대 용량이 존재하고 이 용량 안에서 담을 수 있는 물건의 최대 가치를 찾는다.

 

다이나믹 프로그래밍 , 즉 큰 문제를 작은 문제로 쪼개 푸는 것으로 해결 가능하다.

dp는 이차원 배열로 작성하고 

dp [ 현재 탐색하는 물건 ] [ 가방의 남은 공간 ] = 최대 가치

 

가방 최대 5키로	0 번 물건/3kg	1번 물건	2 번 물건	3 번 물건	4 번 물건
0키로
1키로
3키로
4키로
5키로

 

이런 형태의 표를 생각 할 수 있다

 

..

d[1][6] 은 1번 물건을 담으려 하는데 남은 공간이 6키로라는 의미다.

1번 물건이 3키로에 3달러라 했을 때, 배낭의 최대 가치는 d[i][3] 중 최대 값 +3 달러 일 것이다.

---

d[ i ][ j ] = max ( d[ i−1 ][ j ] , ( i번 물건의 가치 ) + d[ i − 1 ][ j − ( i번 물건의 무게 )])

---

 볼 때마다 새로운 수식이다. 머리에 전혀 남지 않음.

풀때 마다 찾아보는데 그럼에도 문제를 틀린다.ㅜㅋ

ㅋ

d[i−1][j]d[i-1][j]d[i−1][j] : iii번 물건을 선택하지 않은 상태에서의 최대 가치

(i번 물건의 가치)+d[i−1][j−(i번 물건의 무게)](\text{i번 물건의 가치}) + d[i-1][j - (\text{i번 물건의 무게})](i번 물건의 가치)+d[i−1][j−(i번 물건의 무게)] : iii번 물건을 선택하는 경우의 최대 가치