냅색 알고리즘

냅색 문제는 유명한 다이나믹 문제 중 하나이다.

(사진 출처 wikipedia.org)

가장 유치하지만 또 가장 많이 쓰이는 설명으로는,

한 가게에 도둑이 들었다. 도둑이 훔치고 싶은 물건들은 다 각각의 값어치와 무게가 있다.

무게 때문에 도둑은 고를 수 있는 물건이 한정되어 있다.

그러므로 가방에 다 담을 수 있는 내에서 가장 비싼 물건을 훔치고자 한다.

여기서 세 가지 선택이 있다.

1) 모든 경우를 다 세어본다.

물건의 갯수가 n개라면, 각각의 물건은 ( 가방에 넣는가, 안 넣는가 ) 의 두 가지 경우가 있다.

전부 2^n가지의 경우를 세어보면 된다.

2) 넣을 수 있는 가장 비싼 물건부터 넣는다. (Greedy Algorithm)

그럴듯 하지만 생각한것처럼 최적의 해는 나오지 않는다. 예를 들어

$10 / 13 kg

$6 / 6 kg

$5 / 6 kg

가방 15 kg

이라면 6$,5$짜리를 택하는 편이 낫다.

3) 동적 계획법(dynamic programming)을 사용합니다.

dyn[i][j] = (가방의 크기가 i일때, j번째 물건까지 담을 수 있는 경우 최대 가치)라고 하면,

dyn[0][i] = dyn[j][0]= 0 를 base case로 놓을 수 있다.

그렇다면 점화식을 구해보자.

i가 weight[j]보다 크거나 같으면 이 가방엔 이 물건이 들어갈 수 있다.

그렇다면 j번째 물건을 넣는다고 가정했을 때,

((i-weight[j]) 크기의 가방에 (j-1) 번째 물건까지 넣을 수 있는 경우 최대 가치)에다가 value[j]를 더하는 모든 경우가 가능하다.

어느 것이 최대인가는 경우에 따라 다르기 때문에 시도해봐야 한다.

이 물건을 안 넣기로 하거나 가방 크기때문에 넣을 수 없다면,

i번째 가방에 j-1번째 물건을 넣을 수 있는 경우 최대 가치를 그대로 쓸 수 있다.

i≥weight[j]이면 dyn[i][j]=max(dyn[i][j-1],max(dyn[i-weight[j]][j]+value[j]))

i<weight[j]이면 dyn[i][j]=dyn[i][j-1]

이렇게 하면 답은 dyn[가방 크기][마지막 물건].