[알고리즘] 동적 계획법(Dynamic Programming) - 6

동적 계획법(Dynamic Programming) - 6

이번 시간에는 동적 계획법의 또다른 고전 중에 Knapsack Algorithm에 대해 알아보자

Knapsack은 배낭을 가리키는 말인데 배낭 알고리즘 이라고도 한다.

이 알고리즘에는 재미있는 이야기가 숨어있는데, 

도둑이 상점에 물건을 훔치기 위해 배낭 하나를 들고 왔다고 했을 때,

가지고 나갈수있는 무게가 한정적이지만 최대의 비용을 낼 수있게 해야한다.

각각의 물건 마다 무게와 가격이 다 다르다.

따라서 n개의 아이템과 배낭의 용량 W가 주어질 때

배냥의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합을 구해야 한다..

예를 들어 위의 그림에서 {1,2,5}는 가격의 합이 35,

{3,4}는 가격의 합이 40,

{3,5}는 가격의 합이46 이지만 배낭의 무게를 초과한다.

이런 문제를 어떻게 풀어야할까?

가장 먼저 Greedy한 알고리즘을 생각해 볼 수 있다.

그러나 무겁다고 해서 비싼것도 아니고 가볍다고 싼것이 아니다.

그러므로 단위 무게당 가격(가격/무게)이 가장 쉽게 도출해 낼 수 있는 결과이다.

이것을 계산해 보면 위에서부터 1, 3, 3.6, 3.66.., 4의 단위 무게당 가격을 가지는데,

이 때, 그리디 알고리즘에 의해 2번과 5번을 선택 하게되며 결과는 34가된다.

그러나 이는 최선이 아니다.

그러므로 동적계획법을 사용해서 이 문제를 풀어야한다.

동적 계획법을 사용하기 위해서 먼저 순환식을 세워야한다.

여기서 OPT(i, w)는 배낭 용량이 w일 때 아이템 1,2,3...i로 얻을 수 있는 최대 이득을 뜻한다.

이 때 아이템 i를 선택하는 것에 의해 2가지 케이스로 분기된다.

첫번째는 i를 선택 하지 않는 경우는 i는 제외 되지만 용량은 줄어들지 않으므로 w에 변화는 없다.

다른 경우는 i를 선택하는 경우인데 i도 제외되며 용량도 마찬가지로 줄어들게 된다.

결론적으로 위의 순환식을 가지게 된다.

경우 2를 선택 하기 위해서는 조건이 필요한데, 현재 잔여용량 W가 아이템 i의 무게 Wi보다 커야한다.

이러한 조건이 만족될 경우만 경우 2를 선택할 수 있다.

그리고 i가 0이라는 말은 아이템이 더 이상 남아있지 않음을 뜻한다.

결과적으로 슈도 코드는 위와 같이 표현된다.

2차원 배열을 사용해서 표현되며 때문에 2개의 반복문이 사용되었다.

반복문 내부의 조건 분기는 순환식에서 이미 구한 식이다. 

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘