Knapsack problem
도둑이 보석을 훔쳐갈 때, 가방에 들어가는 한도 내에서 가장 비싼 것을 훔쳐가려면 어떻게 해야할까?
Last updated
도둑이 보석을 훔쳐갈 때, 가방에 들어가는 한도 내에서 가장 비싼 것을 훔쳐가려면 어떻게 해야할까?
Last updated
도둑이 보석을 훔쳐가는 상황이다. 가방이 감당할 수 있는 무게 내에서 가장 비싼 값의 보석들을 훔쳐가려면 어떻게 해야할까?
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 알고리즘 : 다항시간 알고리즘이 존재하지 않았고, 앞으로도 존재하지 않을 것이라고 생각되는 알고리즘
