최적화 0-1 knapsack problem (배낭 채우기)

이번 글에서는 동적 알고리즘을 통해 0-1 knapsack problem (배낭 채우기)를 다뤄보도록 하겠습니다. 배낭 채우기 문제는 크게 탐욕 알고리즘을 이용한 fractional knapsack problem과 동적 알고리즘을 이용한 0-1 knapsack problem 이 있습니다. 주어진 배낭(배낭이 담을수 있는 한계 무게가 존재)과 여러 가지 물건(무게와 물건의 가치가 있는)들이 있습니다. 배낭에 최대한 많은 물건을 담으면서 최대한의 가치를 도출해 내는 문제입니다.

 

 

만약 여러분이 시계방을 털었을때 가져온 가방 안에 시계를 10개까지 담을 수 있다고 했을 때 스와치나 티쏘가 아닌 롤렉스나 IWC 같은 고가 혹은 그 이상의 시계를 털어야 한다는 개념(?)인 것입니다. 이것을 배운 도독이라면 제일 비싼 순서대로 10개의 시계를 담을 것입니다. 

 

fractional knapsack problem 알고리즘의 경우 분할이 가능하다는 요상한 조건 때문에 가치/무게 값이 가장 높은 순서대로 담을 수 있기에 탐욕 알고리즘을 통해 간단히 해결되지만 현실은 금덩이가 아닌 이상 분할이 불가능하고 분할하게 되면 그 가치가 없어져 버릴 겁니다.

 

각설하고 서로 다른 무게, 다른 가치의 물건들이 앞에 놓여있을때 주어진 가방이 다 찰 때까지 담아 최대가치를 이끌어 내라라고 한다면 우린 아무 생각 없이 이것저것 넣어보고 빼보고 다시 담아보면서 그 값을 찾아보려 할 것입니다. 이와 마찬가지로 0-1 knapsack problem 역시 이것저것 넣어보고 이 값들을 목록에 적어놓고 최대가치가 되는 조합을 선택하는 것입니다. 

 

물건번호 i	무게 w	가치 v
1	4	7
2	2	5
3	3	6
4	5	9

 

위의 표와 같이 물건1은 무게가 4이고 가치가 8, 물건 2는 무게가 2 가치가 5,.... 물건 4는 무게가 5 가치가 9입니다. 주어진 배낭의 최대 허용 양은 무게 8입니다. 

 

허용된 무게내에서 최대가치 값을 담을 수 있는 물건들에 대해 알아보도록 하겠습니다. 

 

val(i, w)--①{

if(w>=w [i])--②

    max(val(i-1, w)--③ , val(i-1, w-w [i])--④ + v [i]--⑤)

        else

val(i-1, w)--⑥

}

 

val(i, w)는 w무게 내에서 i 번째 물건까지 중 골라 담았을 때의 최대 가치를 의미하고, w>=w [i]에서 W는 현재 배낭에 담을 수 있는 무게 w [i]는 i번째 아이템의 무게를 의미합니다. w>=w [i]는 현재 배낭이 물건 i를 담을 만큼의 무게가 남아있는지 여부입니다. 물건은 총 4개이며 배낭이 담을 수 있는 무게는 8이기 때문에 i =4, w = 8입니다. 

 

이 식을 위의 표를 기준으로 설명하자면 4번째까지의 아이템들을 골라 무게 8 이내로 담을 수 있는 최대가치 값--① 은 만약 4번 아이템을 담을 무게가 있다면--②, 3번째까지의 아이템들을 골라 무게 8 이내로 담을 수 있는 최대가치 값--③ 과 4번 아이템을 이미 담은 배낭에 3번째까지의 아이템들을 골라 4번을 담은 배낭의 무게 내에 담을 수 있는 최대가치 값--④ 에 4번 아이템의 가치를 더한 값--⑤ 중 큰 값을 선택하고 배낭에 4번 아이템을 담을 무게 여유가 없다면 3번째까지의 아이템들을 골라 무게 8 이내로 담을 수 있는 최대가치 값--⑥ 을 선택하는것 입니다. 

 

주어진 식에서 val(4,8)를 구하면 이 문제를 풀 수 있습니다. w= 8이고 w [i]는 5 이기에 8>=5 이니깐 

val(4,8) = if(8>=5) max(val(3,8), val(3,3) + 9) 됩니다. 우리는 val(3,8)과 val(3,3)을 알아내야 합니다.

val(3,8) = if(8>=3) max(val(2,8), val(2,5) + 6) 됩니다. 우리는 val(2,8)과 val(2,5)을 알아내야 합니다.

val(3,5) = if(5>=3) max(val(2,5), val(2,2) + 6) 됩니다. 우리는 val(2,5)과 val(2,2)을 알아내야 합니다.

val(3,3) = if(3>=3) max(val(2,3), val(2,0) + 6) 됩니다. 우리는 val(2,3)과 val(2,0)을 알아내야 합니다.

val(2,8) = if(8>=2) max(val(1,8), val(1,6) + 5) 됩니다. 우리는 val(1,8)과 val(1,6)을 알아내야 합니다.

val(2,5) = if(5>=2) max(val(1,5), val(1,3) + 5) 됩니다. 우리는 val(1,5)과 val(1,3)을 알아내야 합니다.

val(2,3) = if(3>=2) max(val(1,3), val(1,1) + 5) 됩니다. 우리는 val(1,1)을 알아내야 합니다.

val(2,2) = if(2>=2) max(val(1,2), val(1,0) + 5) 됩니다. 우리는 val(1,0)을 알아내야 합니다.

val(2,0) = if(0!>=2) val(1,0)가 됩니다.  val(2,0) = 0 

val(1,8) = if(8>=4) max(val(0,8), val(0,4) + 7)가 됩니다. 즉 val(1,8) = 7

val(1,5) = if(5>=2) max(val(1,5), val(0,1) + 7)가 됩니다. 즉 val(1,5) = 7

val(1,3) = if(!3>=2) val(0,3)가. 즉 val(1,3) = 0

val(1,2) = 0

val(1,1) = 0

 

우리는 필요한 val 값을 다 알아냈습니다. 이를 보기 좋게 표로 정리하면

 

i                w	1	2	3	4	5	6	7	8
1	0	0	0	7(물건 1)	7(물건 1)	7(물건 1)	7(물건 1)	7(물건 1)
2	0	5(물건 2)	5(물건 2)	7(물건 1)	7(물건 1)	12(물건 1,2)	12(물건 1,2)	12(물건 1,2)
3	0	5(물건 2)	6(물건 3)	7(물건 1)	11(물건 2,3)	12(물건 1,2)	13(물건 1,3)	13(물건 1,3)
4	0	5(물건 2)	6(물건 3)	7(물건 1)	11(물건 2,3)	13(물건 1,3)	14(물건 2,4)	15(물건 3,4)

 

위의 표는 물건 1~i까지의 물건을 허용된 w무게까지의 배낭에 담았을 때의 가치(배낭 안에 든 물건들)를 표현한 표입니다. 이렇게 최적의 조건은 4번과 3번 아이템을 택했을 때입니다. 

 

최대한 쉽게 이해될수 있도록 작성했는데 실제로 어떨지는 모르겠네요. 다음 글에서는 저도 여전히 헷갈리는 개념인 NP-Hard, NP-Complete, P에 대해 알아보도록 하겠습니다.