배낭 (평범한 배낭 문제)

d[N][K]는 N번째 물건 까지 살펴보았을 때, 무게가 K인 배낭의 최대 가치 이다.

 

물건을 배낭에 담을 때,

1. 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.

2. 그렇지 않다면, 다음 중 더 나은 가치를 선택하여 넣는다

    2-1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다.

    2-2) 현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다.

 

위 과정을 식으로 나타내면 다음과 같다.

현재 담을 물건의 인덱스를 i, 현재 가방 허용 용량이 j, 현재 담을 물건의 무게를 weight, 가치 value라고 할 때,

① j < weight : d[i][j] = d[i-1][j]

② d[i][j] = max( dp[i-1][j], d[i-1][ j-weight[i] ]+value[i] ) 

dp테이블을 출력했을 때