[[분류:알고리즘]]
[목차]

== 개요 ==
배낭 문제([[背]][[囊]] [[問]][[題]], knapsack problem)는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 [[부분집합]]을 찾는 문제이다. 

[[파일:5-21-1.png|width=400]]

예를 들어, 그림과 같이 어떤 도둑이 열린 상자에 든 금괴를 훔쳐 간다고 가정해보자. 이 때 도둑이 가지고 있는 배낭에 담을 수 있는 총 무게가 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가 된다. 이런 형태의 문제를 '''분할 가능한 배낭 문제'''라고 한다.

[[파일:5-23-5.png|width=400]]

반면에, 이번에는 그림과 같이 열리지 않는 상자에 든 금괴를 훔쳐 간다고 가정해보자. 도둑이 가진 배낭의 총량이 마찬가지로 15kg일 때 도둑이 배낭에 담을 수 있는 최적의 조합은 C 4kg, B 1kg, E 2kg, D 1kg이고 A 상자의 금괴는 담을 수 없다. 왜냐면 상자는 열리지 않기 때문에 A 상자를 열어서 금괴 일부만을 꺼낼 수는 없기 때문이다. 이런 형태의 문제를 '''0-1 배낭 문제'''라고 한다.

== 분할 가능한 배낭 문제 ==
분할 가능한 배낭 문제(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
}}}여기서 W는 최대 무게, w는 무게 배열, p는 가치의 배열이다.

배낭 문제를 [[그리디 알고리즘]]으로 푸는 방법과 위 소스 코드 구현에 대한 자세한 설명은 [[https://youtu.be/8UVDnahV1eg|이 영상]]을 참고할 수 있다.[* [[https://youtu.be/8UVDnahV1eg|배낭 문제와 탐욕 알고리즘 유튜브 강의 영상]]]

== 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)
}}}0-1 배낭 문제를 [[백트래킹]]을 이용하여 파이썬으로 구현한 소스 코드는 아래와 같다.
{{{#!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 배낭 문제를 동적 계획법과 백트래킹으로 푸는 방법과 위 소스 코드 구현에 대한 자세한 설명은 [[https://www.youtube.com/watch?v=uggO0uzGboY|유튜버 A, 동적 계획법]], [[https://youtu.be/A8nOpWRXQrs|유튜버 B, 동적 계획법]], [[https://youtu.be/uWigKsbo3SU|유튜버 B, 백트래킹]]을 참고.
== 변형 문제 ==
무게 대비 가치가 다른 물건들을 일정한 용량의 용기에 담아야 한다는 기본 틀에서, 바리에이션이 많다. 가방이 여러 개인 문제, 고려할 변수가 무게와 가치 외에도 더 있는 3개 이상의 변수 문제 등이 있다.

== 여담 ==
동적 계획법을 사용하면 O(nW)에 구할 수 있기 때문에 이거 다항식 시간 아니냐, 즉 배낭 문제가 P 문제 아니냐고 생각할 수 있다. 반례로써, O(nW)가 P라면, 어떠한 경우에도, 심지어 W=n^n인 경우에도 polynomial time안에 해답을 구할 수 있어야 하지만, 이는 모순이다. 또한, 무게가 정수가 아닌 실수로 주어진다면 동적 계획법을 쓸 수도 없다.

배낭문제의 결정문제, 즉, 가방에 특정 무게 이하로 특정 가치를 가지는 물건을 담을 수 있는가? 를 판단하는 문제는 NP이다. 검산을 다항시간 내에 할 수 있기 때문이다. (이 경우 상수시간이 걸린다.)

또한, 배낭문제의 결정문제는 NP-complete문제인 subset sum으로 환원할 수 있음이 증명되어있다. 배낭문제의 결정문제를 다항시간 내에 풀 수 있으면, 그 방법을 적절히 변환하여 subset sum 문제 또한 다항시간 내에 풀 수 있다는 의미이다. 따라서, 배낭문제의 결정문제는 NP-complete이다.

배낭문제의 결정문제와 별개로, 배낭문제 자체는 최적화를 필요로 한다. 최적화 문제는 결정문제와 또 다른 것으로, 검산을 다항시간 내에 할 수 있는 방법 또한 알려져있지 않다. 따라서, 배낭문제는 NP-hard이다.