들어가며
오늘 알아볼내용은 유명한 Knapsack 문제입니다. 이러한 Knapsack 문제들은 탐욕법(Greedy Algorithm) 또는 동적 계획법(Dynamic Programming)을 사용해서 해결할 수 있습니다.
Knapsack
Knapsack문제는 다음과 같은 상황이 주어집니다. 배낭에 들어갈 수 있는 최대무게가 고정되어있고, 배낭에 들어갈 수 있는 여러 아이템들의 집합이 주어집니다. 여기서, 아이템은 각각 가치와 무게가 있습니다. 이 경우에 배낭에 들어간 아이템들의 가치가 최대가 되도록 아이템을 집어넣는 문제를 Knapsack 혹은 배낭문제라고 불립니다.
예를 들어보겠습니다. 담을 수 있는 무게가 고정되어있는 배낭이 하나있습니다. 그리고 배낭에 넣을 수 있는 금괴들이 담긴 상자들이 있다고 할게요. 각 상자들은 고유한 가치와 무게가 있습니다. 하지만, 금괴를 쪼개어 담을수도 있다고 하겠습니다. 이러한 경우는 쪼갤 수 있는 배낭문제라고 합니다.
다른 예입니다. 마찬가지로 배낭과 금괴가 담긴 상자가 있다고 하겠습니다. 하지만, 이번에는 상자에 담겨져 있는 금괴를 쪼갤 수 없다고 하겠습니다. 이런 경우에는 상자에 담긴 금괴를 전부다 배낭에 넣어야합니다. 이런 경우는 쪼갤 수 없는 배낭문제라고 합니다.
쪼갤 수 있는 Knapsack
쪼갤 수 있는 Knapsack문제는 그리디 알고리즘을 통해서 해결이 가능합니다. 위 상황에서 배낭의 최대무게는 W, 가방에 넣을 수 있는 아이템들은 m개 존재하고, 무게는 w, 가치를 v라고 하겠습니다. 이런 경우에 어떻게 문제를 해결할 수 있을까요? 무게당 가치가 높은 금괴부터 배낭에 집어넣으면 가장 최대가 되도록 금괴를 가방에 넣을 수 있습니다. 거스름돈 문제와 굉장히 유사합니다.
쪼갤 수 없는 Knapsack
쪼갤 수 없는 Knapsack문제는 위처럼 탐욕법으로는 해결할 수 없습니다. 이 경우에는 동적 계획법을 이용할 수 있습니다. 여기서는 DP 테이블을 이중배열로하고, 최대무게가 1씩 증가할 때마다 물건을 하나씩 넣어보면서 최대무게를 구하는 방법으로 풀이할 수 있습니다.
위 상황을 표로 나타내겠습니다.
| 상자 | A | B | C | D | E |
| 무게 | 12 | 1 | 4 | 1 | 2 |
| 가치 | 4 | 2 | 10 | 1 | 2 |
이제, 무게가 0부터 최대무게가 되는 순간까지 각 물건을 배낭에 넣어볼텐데, 배낳에 넣게 되면 여러 상황이 오게됩니다. 첫번째로, 배낭의 남은 허용무게보다 물건의 무게가 큰 경우에는 아예 안넣을 수 있습니다. 두번째로, 넣게 된다면 더 나은 가치를 선택해서 넣을 수 있습니다. 현재 물건의 무게만큼 빼서 현재 물건을 넣던가, 아예 안넣던가죠. 이런식으로 배낭에 금괴를 넣게 되면 아래표처럼 가치의 최대값이 표현됩니다.
| A | B | C | D | E | |
| w=1 | 0 | 2 | 2 | 2 | 2 |
| w=2 | 0 | 2 | 2 | 3 | 3 |
| w=3 | 0 | 2 | 2 | 3 | 4 |
이렇게 쭈욱 진행하면 결국 마지막 DP 값이 정답이 되겠죠? 해당과정을 코드로 작성하면 아래와 같습니다.
# 배낭의 최대 수용 무게
W = 15
# 금괴들
golds = [[0, 0], [12, 4], [1, 2], [4, 10], [1, 1], [2, 2]]
# DP 테이블 초기화
dp = [[0 for _ in range(len(golds))] for _ in range(W+1)]
for w in range(1, W+1):
for n in range(1, 6):
weight = golds[n][0]
value = golds[n][1]
if w < weight:
# 무게가 크면 아예 안넣음
dp[w][n] = dp[w][n-1]
else:
# 그렇지 않으면 더 나은것을 고름.
dp[w][n] = max(dp[w-weight][n-1]+value, dp[w][n-1])
print(dp[15][5])이 코드를 실행하면 배낭에 최대로 넣을 수 있는 금괴상자의 가치인 15가 출력됩니다. B, C, D, E를 넣은 결과입니다.
