Knapsack problem

•

도둑이 보석을 훔쳐가는 상황이다. 가방이 감당할 수 있는 무게 내에서 가장 비싼 값의 보석들을 훔쳐가려면 어떻게 해야할까?

•

N개 아이템과 배낭이 주어진다. 각각의 아이템은 w의 무게와, v의 가격을 가지고 있다.

•

배낭의 용량은 W이다.

•

배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합을 구하고자 한다.

•

보통 이러한 문제는 greedy 적으로 제일 먼저 접근하곤 한다.

◦

1) 가격이 비싼 순서대로 넣거나 2) 무게가 가벼운 순서대로 넣거나 3) 단위 무게당 가격이 높은 것부터 선택하는 방식으로 접근하는데, 안타깝게도 1-3번의 방법 모두 정답을 구할 수 없다.

◦

답은 가격의 합이 40이 되는 {3, 4} 인데, 따라서 이 문제는 greedy 로 풀 수가 없다.

•

순환식을 생각해보자.

•

아이템이 i개가 주어진다고 했을 때, 1부터 i개의 아이템에 대한 무게와 가격정보가 주어질 것이다.

•

이때 우리는 마지막 i번째를 선택하는 경우와 그렇지 않은 경우를 나누어서 생각해볼 수 있다.

◦

i 번째를 선택하지 않는다면, 순환식 OPT(i, w) = OPT(i-1, w) 이 된다.

◦

i번째를 선택한다면, OPT(i, w) = OPT(i-1, W-wi) + vi

▪

단 i번째를 선택하는 경우는 배낭의 무게가 W > wi 를 만족해야한다. 그렇지 않으면, 무조건 첫번째 케이스를 선택할 수 밖에 없다.

•

i-1 값만 고려하면 되므로, 행 우선 계산순서로 진행하면 된다.

•

O(nW)

•

그렇다면 이것은 다항시간인가?

◦

그렇지 않다.

◦

다항시간은 입력 크기에 대한 다항함수일때 성립한다.

◦

이 문제의 경우, 입력받는 값는 n개의 가격과 n개의 무게이므로, 2n이 된다.

◦

그리고 W값은 그냥 주어지는 값이다.

◦

W값을 입력받기 위해 필요한 비트의 수는 logW이다. logW = k라고 한다면, 결국 W = 2^k가 된다.

◦

결국, 이 문제의 시간 복잡도는 O(n2^k)가 되는 것이다.

•

Knapsack problem 은 유명한 NP hard 알고리즘 중 하나이다.

◦

NP-hard 알고리즘 : 다항시간 알고리즘이 존재하지 않았고, 앞으로도 존재하지 않을 것이라고 생각되는 알고리즘