1. 개요
배낭 문제(背囊 問題, knapsack problem)는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다.예를 들어, 그림과 같이 어떤 도둑이 열린 상자에 든 금괴를 훔쳐 간다고 가정해보자. 이 때 도둑이 가지고 있는 배낭에 담을 수 있는 총 무게가 15kg이고, 금괴가 든 상자는 A 상자가 12kg, B 상자가 1kg, C 상자가 4kg, D 상자가 1kg, E 상자가 2kg이 있다고 하자. A, B, C, D, E 상자의 가치가 각각 $4, $2, $10, $1, $2 라고 할때 도둑이 배낭에 담을 수 있는 최적의 조합은 C 4kg, B 1kg, E 2kg, D 1kg, A 7kg가 된다. 이런 형태의 문제를 분할 가능한 배낭 문제라고 한다.
반면에, 이번에는 그림과 같이 열리지 않는 상자에 든 금괴를 훔쳐 간다고 가정해보자. 도둑이 가진 배낭의 총량이 마찬가지로 15kg일 때 도둑이 배낭에 담을 수 있는 최적의 조합은 C 4kg, B 1kg, E 2kg, D 1kg이고 A 상자의 금괴는 담을 수 없다. 왜냐면 상자는 열리지 않기 때문에 A 상자를 열어서 금괴 일부만을 꺼낼 수는 없기 때문이다. 이런 형태의 문제를 0-1 배낭 문제라고 한다.
2. 분할 가능한 배낭 문제
분할 가능한 배낭 문제(fractional knapsack problem)는 그리디 알고리즘으로 풀 수 있다. 아래는 분할 가능한 배낭 문제를 파이썬으로 구현한 소스 코드이다.#!syntax python
def knapsack1(W, w, p):
n = len(w) - 1
K = [0] * (n + 1)
weight = 0
for i in range(1, n + 1):
weight += w[i]
K[i] = w[i]
if (weight > W):
K[i] -= (weight - W)
break;
return K
배낭 문제를 그리디 알고리즘으로 푸는 방법과 위 소스 코드 구현에 대한 자세한 설명은 이 영상을 참고할 수 있다.[1]
3. 0-1 배낭 문제
0-1 배낭 문제(0-1 Knapsack Problem)는 그리디 알고리즘으로는 최적해를 찾을 수 없다. 따라서, 동적 계획법, 백트래킹 등의 조합 최적화 문제의 풀이 방법으로 풀어야 한다.0-1 배낭 문제를 동적 계획법을 이용하여 파이썬으로 구현한 소스 코드는 아래와 같다.
#!syntax python
def knapsack2(i, W, w, p):
if (i <= 0 or W <= 0):
return 0
if (w[i] > W):
value = knapsack2(i - 1, W, w, p)
print(i - 1, W, value)
return value
else: # w[i] <= W
left = knapsack2(i - 1, W, w, p)
print(i - 1, W, left)
right = knapsack2(i - 1, W - w[i], w, p)
print(i - 1, W - w[i], right)
return max(left, p[i] + right)
#!syntax python
def knapsack3 (i, profit, weight):
global maxprofit, numbest, bestset
if (weight <= W and profit > maxprofit):
maxprofit = profit
numbest = i
bestset = include[:]
if (promising(i, profit, weight)):
include[i + 1] = True
knapsack3(i + 1, profit + p[i+1], weight + w[i+1])
include[i + 1] = False
knapsack3(i + 1, profit, weight)
def promising (i, profit, weight):
if (weight > W):
return False
else:
j = i + 1
bound = profit
totweight = weight
while (j <= n and totweight + w[j] <= W):
totweight += w[j]
bound += p[j]
j += 1
k = j
if (k <= n):
bound += (W - totweight) * p[k] / w[k]
return bound > maxprofit
0-1 배낭 문제를 동적 계획법과 백트래킹으로 푸는 방법과 위 소스 코드 구현에 대한 자세한 설명은 유튜버 A, 동적 계획법, 유튜버 B, 동적 계획법, 유튜버 B, 백트래킹을 참고.
4. 변형 문제
무게 대비 가치가 다른 물건들을 일정한 용량의 용기에 담아야 한다는 기본 틀에서, 바리에이션이 많다. 가방이 여러 개인 문제, 고려할 변수가 무게와 가치 외에도 더 있는 3개 이상의 변수 문제 등이 있다.5. 여담
동적 계획법을 사용하면 O(nW)에 구할 수 있기 때문에 이거 다항식 시간 아니냐, 즉 배낭 문제가 P 문제 아니냐고 생각할 수 있다. 반례로써, O(nW)가 P라면, 어떠한 경우에도, 심지어 W=n^n인 경우에도 polynomial time안에 해답을 구할 수 있어야 하지만, 이는 모순이다. 또한, 무게가 정수가 아닌 실수로 주어진다면 동적 계획법을 쓸 수도 없다.배낭문제의 결정문제, 즉, 가방에 특정 무게 이하로 특정 가치를 가지는 물건을 담을 수 있는가? 를 판단하는 문제는 NP이다. 검산을 다항시간 내에 할 수 있기 때문이다. (이 경우 상수시간이 걸린다.)
또한, 배낭문제의 결정문제는 NP-complete문제인 subset sum으로 환원할 수 있음이 증명되어있다. 배낭문제의 결정문제를 다항시간 내에 풀 수 있으면, 그 방법을 적절히 변환하여 subset sum 문제 또한 다항시간 내에 풀 수 있다는 의미이다. 따라서, 배낭문제의 결정문제는 NP-complete이다.
배낭문제의 결정문제와 별개로, 배낭문제 자체는 최적화를 필요로 한다. 최적화 문제는 결정문제와 또 다른 것으로, 검산을 다항시간 내에 할 수 있는 방법 또한 알려져있지 않다. 따라서, 배낭문제는 NP-hard이다.