알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)

탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 

 

둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는

 

동적계획법은 모든 마디를 출발점으로 설정해서 구하기 때문에 과잉이라 볼 수 있다.

 

반면 탐욕 알고리즘은 항상 최적인 해를 만들어 주지 않는다. 그래서 보통 반례를 통해

 

최적의 해를 갖지 않는다는 것을 증명한다. 

 

이 두 방법의 차이점을 확실하게 이해하기 위해서 0-1배낭 채우기와 배낭 빈틈없이 채우기라고 하는

두가지 문제를 살펴본다. 

 

우선 결론적으로 말하면 배낭 빈틈없이 채우기 문제는 탐욕 알고리즘을 이용해서 풀 수 있지만 

 

0-1배낭채우기를 풀 수 없으며 대신 동적계획법을 이용해서 완벽하게 풀 수 있다. 

 

 

 

 

 

< 0-1배낭채우기 문제(0-1 knapsack problem) >

 

도둑 하나가 보석상에 침입했다고 하자. 훔친 물건들의 총 무게가 배냥의 용량 W를 초과하면 

 

배낭이 찢어진다. 각 물건들의 값어치와 무게를 알고 있다고 했을때, 도둑은 W를 넘지 않으면서

 

챙긴 물건들의 총 값어치가 최대가 되도록 배낭에 물건을 담고 싶다. 

 

이를 0-1 배낭채우기 문제 (0-1 knapsack problem)이라고 한다. 

 

 

 

 

이를 일반화시켜보면 item이 n개 있다고 가정했을 때 

 

 

 

이 문제를 brute force로 풀었을 때 각각의 경우에 대해서 item을 넣고 빼는 

 

경우이므로 2의 n거듭제곱 만큼의 시간이 걸린다. 

 

 

그렇다면 이 문제를 탐욕적인 알고리즘으로 풀 수 있을까?

 

가장 일반적이고 쉬운 탐욕 알고리즘은 가장 값어치가 큰 아이템을 먼저 선택하는 경우지만 

이 방법은 해결책이 되지 못한다. 

 

마찬가지로 무게당 값어치가 가장 높은 아이템을 우선적으로 채운다고 했을 때 이 또한

0-1배낭채우기 문제를 풀 수 없다.

 

 

반면 이 경우에 대해서는 배낭 빈틈없이 채우기 문제(fractional knapsack problem)을 풀 수 있다. 

 

이 문제에서는 애초에 아이템을 조각내어 배낭의 남은 부분까지 채울 수 있다고 가정하기 때문에

 

탐욕적인 방법으로 무게당 값어치가 많이 나가는 아이템을 순서대로 선택한다면 

이 문제를 풀 수 있다. 

 

 

 

 

결론적으로 말하면 0-1배낭채우기 문제는 탐욕알고리즘으로 풀 수 없으며 동적계획법을

이용해서 풀어야 한다.

 

 

i > 0 이고 w > 0일 때, 전체 무게가 w가 넘지 않도록 i번째까지의 항목 중에서

  얻어진 최고의 이익(optimal profit)을 P[i][w]라고 하면, 다음과 같이 나타낼 수 있다.

 

 

여기서 P[i -1][w]는 i번째 항목을 포함시키지 않았을 때 최고 이익이 되는 경우,

 

pi + P[i-1][w - wi]는 i번째 항목을 포함시켰을 때 최고 이익이 되는 경우다.

 

위의 재귀 관계식이 최적화 원칙을 만족하는지는 쉽게 알 수 있다.

 

그러므로 최대이익은 P[n][W]가 되고 계산할 배열의 엔트리 수는 

 

이다. 

 

 

 

 

 

하지만 n과 W는 어떠한 상관관계도 없기 때문에 만일 임의적으로 W = n!이라고 한다면

 

수행시간은 n x n! 으로 앞에서 설명한 brute force 알고리즘 보다 좋을게 없다.

 

 

그렇다면 이 알고리즘을 bruteforce보다 비슷하거나 종종 더 빠른 경우로 개선할 수 없을까?

 

 

1과 W 사이에 있는 모든 w에 대해서 i번째 행은 계산할 필요가 없다는 사실을 착안점으로 

 

개선을 시도한다. n번째 행에서는 P[n][W]만 계산하면 된다. 

 

그리고 다른 행에 대해서도 이를 적용한다. 

 

 

 

 

 

 

이렇게 봤을 때는 이해가 잘 되지 않으므로 예를 들어보자 

 

다음과 같은 리스트가 있을 때 P[3][30]을 구해보자

 

 

P[3][30] = max(P[3-1][30], p3 + P[3-1][30-w3])

            = max(P[2][30], p3 + P[2][10])

 

P[2][30] = max(P[2-1][30], p2 + P[2-1][30-w2])

            = max(P[1][30], p2 + P[1][20])

 

P[2][10] = max(P[2-1][10], p2 + P[2-1][10-w2])

            = max(P[1][10], p2 + P[1][0])

 

 

 

이제 1행에 대해서 계산한다.

 

P[1][0] = $0;  P[1][10] = $50;  P[1][20] = $50;  P[1][30] = $50

 

 

 

1행에서 계산한 값을 이용해 P[3][30]을 구한다. 

 

P[2][10] =  max(P[1][10], $60+P[1][0]) (if w2 = 10 < 10)

       or = P[1][10]                          (if w2 = 10 > 10)

          = $60

 

P[2][30] =  max(P[1][30], $60+P[1][20]) (if w2 = 10 < 30)

       or =  P[1][30]                           (if w2 = 10 > 30)

           = $60 + $50 = $110

 

P[3][30] =    max(P[2][30], $140+P[2][10]) (if w3 = 20 < 30)

       or =  P[1][10]                              (if w3 = 20 > 30)

           = $140 + $60 = $200

 

 

 

원래의 알고리즘에서는 90개의 엔트리를 계산하는 반면

 

개선된 알고리즘에서는 7개의 엔트리만 계산하여 값을 도출해내었다. 

 

위와 같은 방식으로 알고리즘을 개선해서 최악의 경우 시간복잡도를 2의 n거듭제곱만큼으로 

끌어올렸다. 

 

결론적으로 위의 결과들을 종합시켜보면 

를 얻을 수 있다.