The Knapsack Problem (배낭 문제)

카테고리 없음

The Knapsack Problem (배낭 문제)

H0CHI 2024. 7. 21. 04:24

The Knaspack Problem

배낭을 메고 있는 도둑이 보석상에 들어갔다. 도둑은 보석을 배낭에 담아 훔쳐야 한다. 배낭에 담을 수 있는 최대 무게가 정해져 있을 때, 도둑이 훔칠 수 있는 최대 보석의 가치는 얼마일까?

위는 Knapsack Problem의 내용이고, 다음과 같이 수식으로 표현할 수 있다.

$$ S = \{ item_1, item_2, ..., itme_n \} $$

$$ w_i = item_i의 무게 $$

$$ p_i = tiem_i의 가치 $$

$$ W = 배낭에 넣을 수 있는 최대 무게 $$

Knapsack Problem에서 원하는 값은 무게의 합이 $ W $보다 작으면서 ($ \sum_{item_i \in A} w_i \le W $) 가치의 합 ($ \sum_{item_i \in A} p_i $) 이 최대가 되는 $ S $의 부분집합 $ A \subseteq S $를 찾는 문제이다.

Brute Force Approach

아이템을 담을 수 있는 모든 경우의 수를 계산한다. 모든 경우에서 $ W $를 초과하지 않는 조합 중 가장 큰 가치의 합을 구하면 된다. 이 방식의 복잡도는 아이템 개수 $ n $에 대해 $ O(n^2) $이 된다.

다른 풀이법으로 gready approach를 해 볼수가 있다.

1. 가장 가치가 높은 아이템부터 추가

2. 가장 무게가 낮은 아이템부터 추가

결과적으로는 두 방법 모두 최적해를 보장하지 못하고, 어렵지 않게 반례를 만들 수 있다.

The Fractional Knapsack Problem

Fractional Knapsack Problem은 보석을 쪼갤 수 있다. 즉 아이템을 조각내어 배낭의 남은 부분에 채울 수 있게 된다. 해당 문제는 모든 보색을 무게 단위로 쪼개고, 무게당 값어치가 높은 아이템을 먼저 담는 방식의 greeady approach를 통해 해결 가능하다.

Fractional Kanpsack Problem에서는 배낭에 빈 공간이 없이 보석을 채울 수 있고, 무게당 값어치가 높은 아이템을 먼저 채워 최적의 해를 보장할 수 있다.

The 0-1 Knapsack Problem

0-1 Knapsack Problem은 Fractional Problem과 같이 보석을 쪼갤 수 없다. 즉 하나의 보석을 담거나 담지 않아야 한다.

Fractional Problem과 동일하게 무게당 값어치가 높은 가격을 먼저 담는 gready approach를 시도해 볼 수 있다. 하지만 이 방법은 최적의 해를 보장하지 않는다.

품목	무게	값
item1	25lb	$10
item2	10lb	$9
item3	10lb	$9

위의 예시의 경우 무게당 값어치가 가장 높은 아이템은 1번이다. $ W $가 30인 경우 무게당 값어치가 가장 높은 1번 아이템을 먼저 배낭에 담는다. 이런 경우 gready approach를 사용하면 $ item_1 $만을 담아 $10의 이득을 취한다. 하지만 최적의 해는 $ item_1 $을 담지 않고, $ item_2, item_3 $을 담아 $18의 이득을 취하는것이 최적의 해이다.

즉 0-1 Kanpsack Prblem은 gready approach로 최적의 해를 보장하지 못한다. 그래서 해당 문제를 해결하기 위해서는 dynamic programming approach를 사용해야 한다.

$ A $가 $ n $개 아이템들 중 최적을 이루는 부분집합이라 하면, $ A $는 $ item_n $을 포함하거나 포함하지 않는다. 그러면 $ A $에 속한 아이템의 총 이익은 $ n - 1 $개 아이템들 중에서 최적을 이루는 부분집합의 아이템 총 이익과 같거나($ item_n $을 포함하지 않는 경우), 그 부분집합의 아이템 총 이익에 $ p_n $을 더한 값이다. ($ item_n $을 포함하는 경우)

이를 일반화 하면 $ i > 0 $, $ w > 0 $인 경우 총 무게가 $ w $를 초과할 수 없다는 제약조건 하에 처음 $ i $개 아이템에서만 선택할 때 얻는 최적의 이익을 $ P[i][w] $라고 하면, 다음과 같은 식을 얻을 수 있다.

$$ P[i][w] = \begin{cases} maximim(P[i - 1][w], p_i + P[i - 1][w - w_i]) & w_i \le w \\ P[i - 1][w] & w_i > w \end{cases} $$

여기서 $ P[i - 1][w] $는 $ i $번째 항목을 포함시키지 않는 경우의 최고 이익이고, $ p_i + P[i - 1][w - w_i] $는 $ i $번째 항목을 포함시키는 경우의 최고 이익이다. 문제의 정답인 $ W $무게를 초과하지 않고 $ n $개 아이템을 선택해 얻은 최적의 이익은 $ P[n][W] $이다.

Complexity of 0-1 Knapsack Problem

$ P[n][W] $를 계산하기 위해서는 $ P[0..n][0..W] $의 2차원 배열을 만들고, 2차원 배열의 값을 채우는 연산이 필요하다. 그럼 시간과 공간 복잡도는 $ O(nW) $이다. 하지만 배낭의 무게 제한 $ W $는 아이템의 개수와 무관하고, 만약 $ n! $만큼 큰 값이라면 이는 brute force 방식보다 큰 값이 된다.

즉 0-1 Knapsack Problem의 실질적 복잡도는 다음과 같다.

$$ O(minimum(2^n, nW)) $$

Improve method of Space Complexity

$ P[i][w] $값을 계산하기 위해 필요한 값은 $ P[i - 1][w] $ 또는 $ P[i - 1][w - w_i] $ 이다. 즉 $ i $번째 행에 대해 연산을 진행할 때 필요한 행은 직전 행인 $ i - 1 $행이다. 그러면 2차원 배열의 행 개수를 $ n $만큼 선언하는 것이 아닌, 2개만 선언하여 $ P[(i - 1) \% 2][w] $, $ P[i \% 2][w] $로 사용할 수 있다.

하지만 열에 대해서도 분석을 하면, 이전 행의 이전 또는 자신의 열만 사용하고 있다. 그러면 2차원 배열 대신 1차원 배열을 $ n $번 갱신하는 방법을 사용해서 공간 복잡도를 개선할 수 있다.

$ i - 1 $까지 계산되었다고 생각하자. 그리고 $ i $번째 단계를 진행할 때, $ P[w] $의 값은 $ P[i - 1][w] $이다. $ i $번째 단계에서 $ w $열의 값 $ P[w] $는 현재 그 자리에 있는 값 $ P[w] $ ($ P[w] = P[i - 1][w] $)와 $ w - w_i $열에 있는 값 $ P[w - w_i] $ ( $P[w - w_i] = P[i - 1][w - w_i] $)에 $ p_i $를 더한 값 중의 큰 값이다.

따라서 $ w = W $부터 $ w = 0 $으로 감소 시키며 $ P[w] $를 갱신하면 1차원 배열을 통해서 계산이 가능하다.

결론적으로 0-1 Knapsack Problem의 공간 복잡도는 $ O(n) $이 된다. (dynamic approach를 사용하는 경우)