[[분류:알고리즘]] [목차] == 개요 == 배낭 문제(Knapsack Problem)는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. [[파일:5-21-1.png|width=400]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] 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|width=400]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.632, 책만, 2020 반면에, 이번에는 그림과 같이 열리지 않는 상자에 든 금괴를 훔쳐 간다고 가정해보자. 도둑이 가진 배낭의 총량이 마찬가지로 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 }}} 배낭 문제를 [[그리디 알고리즘]]으로 푸는 방법과 위 소스 코드 구현에 대한 자세한 설명은 [[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://youtu.be/A8nOpWRXQrs|이 영상]]과 [[https://youtu.be/uWigKsbo3SU|이 영상]]을 참고할 수 있다. [* [[https://youtu.be/A8nOpWRXQrs|0-1 배낭 문제와 동적 계획법 유튜브 강의 영상]]] [* [[https://youtu.be/uWigKsbo3SU|0-1 배낭 문제와 백트래킹 유튜브 강의 영상]]] == 변형 문제 == 무게 대비 가치가 다른 물건들을 일정한 용량의 용기에 담아야 한다는 기본 틀에서, 바리에이션이 많다. 가방이 여러 개인 문제, 고려할 변수가 무게와 가치 외에도 더 있는 3개 이상의 변수 문제 등이 있다.