조합 최적화란?
현실세계에서 발생하는 최적화 문제는 대부분 효율적인 알고리즘을 가지지 않는 NP-Hard 문제에서 어떻게 최적화를 할지에 관한 것. 보통 문제 공간이 크기 때문에 조합 최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데에 중점을 둔다.
KanpSack Problem
배낭 문제. 조합 최적화의 유명한 문제다.
간단하게 말하자면 한 여행자가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제다.
이 배낭 문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(무게가 자연수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭 문제를 분할가능 배낭문제(Fractional Knapsack), 짐을 쪼갤 수 없는 경우의 배낭 문제를 0-1 배낭문제(0-1 Knapsack Problem)이라고 부른다.
이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적 계획법 등으로 의사 다항 시간에 풀 수 있다. (다항시간, 의사다항시간이 뭐지?) 단, 쪼갤 수 없는 경우에는 NP-Complete 문제기 때문에 알려진 다항 시간 알고리즘은 없다.
문제 접근 방법
이 문제를 보면 딱 생각나는 방법은 두가지 정도가 있다.
1. 모든 경우의 수를 넣어보기 (brute force)
가능한 모든 부분집합을 고려하는 방법이다.
단, 물건의 갯수가 n개라면 $n^2$의 경우를 세봐야 하기 때문에, 데이터가 큰 경우에는 적절하지 않다.
2. 넣을 수 있는 가장 무거운 물건부터 넣어보기 (Greedy)
물건을 쪼갤 수 있는 경우에는 괜찮으나, 그렇지 않은 경우에는 최적의 해는 나오지 않는다.
3. 동적 계획법 사용하기
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[가방 크기][마지막 물건]이 된다.