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

파일:5-21-1.png
<파이썬 알고리즘 인터뷰> p.587, 책만, 2020

예를 들어, 그림과 같이 어떤 도둑이 열린 상자에 든 금괴를 훔쳐 간다고 가정해보자. 이 때 도둑이 가지고 있는 배낭에 담을 수 있는 총 무게가 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
<파이썬 알고리즘 인터뷰> p.632, 책만, 2020

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

분할 가능한 배낭 문제(Fractional Knapsack Problem)는 그리디 알고리즘으로 풀 수 있다. 아래는 분할 가능한 배낭 문제를 파이썬으로 구현한 소스 코드이다.

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]

0-1 배낭 문제(0-1 Knapsack Problem)는 그리디 알고리즘으로는 최적해를 찾을 수 없다. 따라서, 동적 계획법, 백트래킹 등의 조합 최적화 문제의 풀이 방법으로 풀어야 한다.

0-1 배낭 문제를 동적 계획법을 이용하여 파이썬으로 구현한 소스 코드는 아래와 같다.

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 배낭 문제를 백트래킹을 이용하여 파이썬으로 구현한 소스 코드는 아래와 같다.

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 배낭 문제를 동적 계획법과 백트래킹으로 푸는 방법과 위 소스 코드 구현에 대한 자세한 설명은 이 영상과 이 영상을 참고할 수 있다. [2] [3]

무게 대비 가치가 다른 물건들을 일정한 용량의 용기에 담아야 한다는 기본 틀에서, 바리에이션이 많다. 가방이 여러 개인 문제, 고려할 변수가 무게와 가치 외에도 더 있는 3개 이상의 변수 문제 등이 있다.