0-1 배낭 문제(0-1 Knapsack Problem)
목표
배낭의 용량을 넘지 않으면서 가치가 최대가 되는 $S$의 부분집합 $A$ 찾기
Notation
- n개의 아이템 집합 : $S = {item_1, item_2, \ldots , item_n}$
- 아이템의 무게 : $w=[w_1,w_2,\ldots,w_n]$
- 아이템의 가치 : $p = [p_1,p_2,\ldots,p_n]$
- 배낭의 용량 : $W$
- 배낭의 용량 조건 : $\Sigma_{item_i\in A}w_i \le W$
- 가치 평가 함수 : $\Sigma_{item_i\in A} p_i$
- memoization(tabulation)(값을 저장하는 이차원 배열) : $P$
배낭 문제(Knapsack Problem)의 분류
분할 가능한 배낭 문제(fractional knapsack problem)
후보군의 아이템을 온전히 담지 않고, 일부(예 : 잘라서)만 담는 것이 허용되는 문제
무게대비 가치가 높은 순서대로 정렬하고 순서대로 담은 뒤, 남은 무게만큼 분할하여 가득 채우는 그리디 알고리즘 방식으로 최적해를 찾을 수 있다.
0-1 배낭 문제 (0-1 knapsack problem)
분할 가능한 배낭 문제와 달리 후보군의 아이템을 온전히 담아야 하는 문제
그리디 알고리즘으로 최적해를 찾을 수 없다. 동적 계획법, 백트래킹 등의 조합 최적화 방식으로 푼다.
포스팅에서 중점적으로 다루고자 하는 것은 DP를 통한 0-1 배낭 문제의 해결이다.
동적 계획법(Dynamic Programming)
간단하게 설명하자면,
- 재귀 방식으로 구현하는 Top-Down 방식과
- 반복문을 이용하여 구현하는 Bottom-Up 방식이 존재한다.
자세한 설명은 다음 링크를 참고하면 좋을 것 같다.
문제 풀이 아이디어
우선 DP로 문제를 풀기 위해서는 문제가 최적 부분 구조를 가진다고 증명해야 한다.
간단하게 만약 A를 n개의 아이템($S$) 중에서 최적(가장 높은 가치를 가지는)을 이루는 부분집합이라고 가정한다면,
이때 A가 $item_n$을 포함하는 부분 집합인 경우와 포함하지 않는 부분 집합인 경우 두 가지로 나눌 수 있다.
- 만약 $item_n$을 포함하지 않는다면, A는 n-1개 아이템들($S-item_n$) 중에서 최적을 이루는 부분집합과 같다.
- 만약 $item_n$을 포함한다면 A에 속한 아이템들의 총 무게는 $W - w_n$을 초과하지 않는다는 조건 하에 n - 1개의 아이템들을 선택하여 얻는 최적의 이익에 $p_n$을 더한 것과 같다.
따라서 이전의 결과 값을 사용해도 최적해가 보장되는 최적 부분 구조임을 알 수 있다.
문제 풀이를 위해 memoization을 진행할 $P$ 라는 2차원 배열을 정의한다.
P의 예시
- $P[i][w]$ : 총 무게가 $w$를 초과할 수 없다는 제약조건 하에서 처음 i개 아이템에서만 선택할 때 얻는 최적의 이익
- $P[n][w]$ : n개의 아이템으로 얻을 수 있는 최대 이익
앞서 언급한 두 가지 경우를 고려하여 가치를 최대화 해야하므로 다음과 같은 점화식을 도출할 수 있다. \(P[i][j]=\max(P[i-1][j],P[i-1][j-w_i]+p_i)\) 즉, j무게를 사용하는 경우 i번째 아이템까지 포함했을 때는 두 경우 중 최댓값을 사용하게 된다.
예시를 통한 유도 과정은 다음 유튜브를 참고하면 좋을 것 같다.