0-1 Knapsack Problem
0-1 Knapsack Problem
0-1 Knapsack problem
- 각 무게가 w_i, 가치가 v_i 인 n개의 물건이 있음
- 이 중 몇 개의 물건을 선택해 총 무게의 합은 W 이하가 되게 하며, 가치들의 합의 최대값을 찾는 문제
Basic Idea
- DP로 해결 가능. 각 물건들에 번호를 1, 2, …, n번까지 부여
- 다음과 같은 배열을 생각 가능
m[i, w]: 총 무게의 합이 w이하 이고, i번째 물건 까지만 사용했을 때 가치들의 합의 최대 값m[i, 0]및m[0, w]는 0임- i <= n, w <= W 이므로 m의 크기는 nW임.
Main Idea
만약 i번째 물건의 무게, w_i가 w보다 크면 다음 식이 성립
- i번째 물건은 절대 담을 수 없으므로, i - 1번째 물건 까지만 사용한 가치 최대값과 동일
m[i, w] = m[i - 1, w]
만약 i번째 물건의 무게, w_i가 w보다 작으면 다음 식이 성립
- i번째 물건을 넣은 것의 가치 최대값과 안 넣은 것의 가치 최대값을 비교해야 함
- i번째 물건을 넣지 않은 것의 가치 최대값은
m[i - 1, w] - i번째 물건을 넣은 것의 가치 최대값은
m[i - 1, w - w_i] + v_i m[i, w] = max(m[i - 1, w], m[i - 1, w - w_i] + v_i)
m[n, W]가 문제의 답이 됨
Time Complexity
- 각 물건들이 들어갔을 때와 안 들어갔을 때를 나눠 모든 경우를 확인한다면
O(2^n)의 시간 복잡도 - 하지만 위 방법을 이용하면 공간 및 시간 복잡도 모두
O(nW)임