Knapsack problem - Dynamic Program

중요한 알고리즘 세 가지중 하나인 Dynamic Program 의 유명한 예제인 백준 12865번 배낭문제를 풀어보았다.

 

Knapsack problem은 주어진 무게 제한 안에서 각 아이템들의 무게와 가치를 조합하여 수 있는 최대 가치를 구하는 문제이다. 

 

해당 문제를 Dynamic Program으로 접근하는데에는 이유가 있다.

우선 단순 접근법으로 해당 문제를 푼다면 item 하나당 선택 또는 비선택의 경우를 고르게 되므로 총 2^n 이란 시간이 걸린다. 

Greedy Algorithm 으로 해당 문제를 접근한다면 어떤것을 greedy 전략으로 선택해야할지 골라야 하는데 

value 값이 큰 것부터 선택하게 된다면 optimal한 solution을 가지지 못하는 경우가 생긴다.

그렇다고 무게가 적은 것 부터 선택하게 된다고 optimal한 solution을 가지게 된다고 확신할 수 없다.

따라서 해당 문제는 DP를 이용하여 접근하는 것이 맞는 것이다. 

 

 

아래와 같이 DP를 이용하여 문제를 풀때에는 먼저 optimal solution의 case를 나누어 설계하는 것이 중요하다. 

그 다음으로는 recursive step을 거쳐 DP테이블을 채워 값을 찾으면 된다. 

 

Knapsack problem은 크게 두 가지 경우로 나눌 수 있다. 

Case 1 : item i를 선택하는 경우 

Case 2 : item i를 선택하지 않는 경우

 

이것을 Recursive step으로 표현한다면 

 1. item i의 무게가 더 이상 가방에 들어갈 수 없는 경우 : (i 가 자명하게 들어가지 않으므로 그 전까지 비교한 것과 동일)

      OPT(i,w) = OPT(i-1, w) 

2. item i의 무게가 가방에 들어갈 수 있는 경우 : 

     OPT(i,w) = max ( OPT(i-1, w) , v(i) + OPT(i-1, w-w(i)) )

-> i 가 들어갔을 때와 들어가지 않았을때의 OPT값을 비교하여 큰 것을 선택하여 테이블에 적는다. 

 

위에서 말한 과정을 따라하면 아래 사진과 같이 테이블이 채워지고 마지막값으로 최대 가치를 구할 수 있게 된다. 

 

---

마지막으로 해당문제를 Java코드로 푼 것으로 포스팅을 마친다.