동적 계획법(5) - Knapsack

Dynamic Programming (5)

Knapsack Problem

- n개의 물건과 배낭이 있다.

- 각 물건은 무게 $w_i$와 가격 $v_i$를 가진다.

- 배낭의 용량은 W라고 한다.

- 목적 : 배낭의 용량을 초과하지 않는 선에서 가격이 최대가 되는 부분집합을 찾는다.

- Ex) 배낭의 용량은 11이라 한다.

i = {1, 2, 5}는 가격의 합이 35가 된다.

i = {3, 4}는 가격의 합이 40이 된다.

i = {3, 5}는 46이 되나 배낭의 용량인 11을 초과하게 된다.

- 문제 해결 방식 : Greedy

1) 가격이 높은 것부터 선택한다.

2) 무게가 가벼운 것부터 선택한다.

3) 단위 무게당 가격이 높은 것부터 선택한다.

∴ 단순한 접근으로는 최적의 답을 찾을 수 없게 된다.

 

Knapsack - 순환식

- OPT(i) : 물건 1, 2, ... , i로 얻을 수 있는 최대의 가격

1) case 1 : 물건 i를 선택하지 않는 경우

OPT(i) = OPT(i - 1)

2) case 2 : 물건 i를 선택하는 경우

OPT(i)의 값을 알 수 없게 된다.

- OPT(i, w) : 배낭의 용량이 w일 때 물건 1, 2, ... , i로 얻을 수 있는 최대 가격

1) case 1 : 물건 i를 선택하지 않는 경우

OPT(i, w) = OPT(i - 1, w)

2) case 2 : 물건 i를 선택하는 경우 (단, 잔여 용량인 W가 $w_i$보다 많거나 같아야 한다.)

OPT(i) = OPT(i - 1, W - $w_i$) + $v_i$

우리는 경우 1과 2중 어떤것이 더 좋은 결과를 도출하는지 알 수 없기 때문에 두 값을 모두 구한 후 더 큰 값을 최종적인 결과물로 반환하면 된다.

- 최종적으로 도출되는 경우들의 계산법은 아래와 같다.

 

Knapsack - BottomUp으로 답을 찾는 과정

- 슈도 코드

knapsack (n, W, w, v) // w와 v는 배열

for w = 0 to W

M[0, w] = 0;

for i = 1 to n

for j = 1 to W

if (w[i] > j)

M[i, j] = M[i - 1, j];

else

M[i, j] = Math.max (M[i - 1, j], v[i] + M[i - 1, j - w[i]]);

return M[n, W];

 

Knapsack의 시간 복잡도

- O(nW)의 시간이 소요된다.

- 다항 시간인가의 여부

다항 시간이라는 것은 입력 크기에 대한 다항함수일 때 성립된다. (Ex. O($n^2$))

Knapsack에서 n은 입력된 크기이나 W는 입력으로써 주어지는 값 자제이기 때문에 다항 시간이라고 볼 수 없다.

현재까지도 다항 시간을 가지고 있는 알고리즘은 존재하지 않으며 앞으로도 나오기 힘들 것으로 알려져있다.