Knapsack, 즉 배낭문제는 DP의 한 유형으로,
두 가지 기준에 알맞게 최적값을 구하는 유형의 DP이다.
이 냅색 알고리즘 문제를 몇 개 풀었었는데,
안풀다보니 풀이 방법을 까먹을 때가 많아…한번 제대로 정리해보려 한다.
Kanpsack은 ‘배낭’을 의미하는 단어이며,
문제상황은 위와 같다.
15kg의 Capacity를 지닌 배낭에 물건을 담아야 하는데,
5개의 물건이 지닌 무게와 가치($)는 각각 다르다.
이때 가장 많은 가치를 가지도록 물건을 담으려면 어떻게 해야 할까?
이 문제의 핵심은 기준이 무게 / 가치 로 2개가 존재한다는 점이다.
기준이 2가지이므로 Greedy하게 풀 수가 없는데,
무게를 우선시하는 경우와 가치를 우선시하는 경우 모두 최적해가 아닐 가능성이 있기 때문이다.
무게가 많이 나가지만 가치가 별로 없을 수 있고,
반대로 가치는 높으나 무게가 많이 나가서 다른 짐들을 같이 넣지 못할 수도 있다.
만약 이 문제를 brute force로 접근한다면,
짐을 넣는다/넣지 않는다로 두 가지의 경우가 나오기 때문에,
총 경우의 수는 2^(짐의 개수) 로 exponential한 복잡도가 나와서 성능이 좋지 않게 된다.
따라서 우리는 Dynammic Programming을 활용하여,
각 경우마다의 최적값만을 memoization하여 성능을 높일 것이다.
우선 대표적인 문제로는 백준의 평범한 배낭 문제가 있다.
위 문제에 예시로 주어진 조건은
- 짐 개수 : 4개
- 배낭 무게 제한 : 7
- 각 짐의 무게와 가치
- (6, 13), (4, 8), (3, 6), (5, 12)
우리는 memoization을 위한 dp배열을 아래와 같이 생각해볼 수 있다.
dp [ 짐의 숫자 ] [ 남아있는 배낭의 무게 ] = 최대 가치
이 때 가방에 아무것도 넣지 않았을 경우는 가치가 0 이므로 0으로 초기화하고,
나머지는 -1로 초기화해준다 (필요한 경우만 갱신하기 위함).
우선 첫 번째 짐에 대한 dp를 표로 그리면 아래와 같다.
| 짐 순서 / 무게 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1번 짐 | -1 | 13 | -1 | -1 | -1 | -1 | -1 | 0 |
1번 짐의 무게는 6, 가치는 13이므로,
1번 짐을 넣었을 때 넣을 수 있는 남은 배낭의 무게는 1, 그 상태에서의 최대 가치값은 13이 된다.
이제 2번 짐을 넣었을 때의 결과를 보자.
| 짐 순서 / 무게 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1번 짐 | -1 | 13 | -1 | -1 | -1 | -1 | -1 | 0 |
| 2번 짐 | -1 | 13 | -1 | 8 | -1 | -1 | -1 | 0 |
1번짐을 넣었을 때의 결과 행을 보고 -1이 아닌 경우만 2번 짐을 넣는데,
1번 짐을 넣었을 때 넣을 수 있는 배낭 무게가 1밖에 남지 않았으므로 1번과 2번 짐을 동시에 넣을 수 없지만,
가방 무게가 1 남았을 때의 최대 가치는 여전히 13이므로 그대로 13을 넣어준다.
왜냐하면 dp값이 의미하는 것은 현재 남아있는 배낭 무게에서의 최대 가치이기 때문이다.
2번 짐만 넣었을 경우 남아있는 배낭 무게는 3, 최대 가치는 8 이므로 8을 넣어준다.
이제 3번 짐을 넣었을 때의 결과를 보자.
| 짐 순서 / 무게 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1번 짐 | -1 | 13 | -1 | -1 | -1 | -1 | -1 | 0 |
| 2번 짐 | -1 | 13 | -1 | 8 | -1 | -1 | -1 | 0 |
| 3번 짐 | 14 | 13 | -1 | 8 | 6 | -1 | -1 | 0 |
3번짐은 무게가 3, 가치가 6이므로
3번 짐을 단독으로 넣거나, 2번짐을 넣고 남은 가방무게가 3인 경우에 3번 짐을 넣을 수 있다.
전자의 경우 남은 무게가 4이므로 6을 표시해주면 되고,
후자의 경우 남은 무게가 0이고 가치의 최대값은 14가 된다.
이제 마지막 4번 짐을 넣었을 때의 경우를 보자.
| 짐 순서 / 무게 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1번 짐 | -1 | 13 | -1 | -1 | -1 | -1 | -1 | 0 |
| 2번 짐 | -1 | 13 | -1 | 8 | -1 | -1 | -1 | 0 |
| 3번 짐 | 14 | 13 | -1 | 8 | 6 | -1 | -1 | 0 |
| 4번 짐 | 14 | 13 | 12 | 8 | 6 | -1 | -1 | 0 |
4번 짐은 무게가 5, 가치가 12이므로
무게가 7남았을 때의 경우 최대값 + 12로 남은무게 2를 각각 갱신해주면 된다.
즉 이 경우 가방의 무게 경우의 수가 7, 4, 3, 1, 0 이므로, 무게 5를 넣을 수 있는 경우는 7일 때 뿐이다.
이렇게 해서 나온 최대값 14가 바로 위 예시의 정답이 된다.
이처럼 냅색 알고리즘은 아이디어 자체는 굉장히 단순하나,
이 개념을 모르고 있다면 풀이에 상당히 애를 먹을 수 있는 문제 유형이다.
따라서 개념을 잘 숙지하고, 문제를 많이 풀어본다면 풀이방법을 잘 익힐 수 있을 것이다.
내가 풀어본 약간 변형된 Knapsack 유형의 문제는 백준의 카우버거 알바생 문제이다.
기준이 하나 더 추가되었지만, 점화식을 잘 숙지하면 그렇게 어렵지는 않다.
정답 소스
import sys
N, M, K = map(int, sys.stdin.readline().split(" "))
dp = [[-1] * (K + 1) for _ in range(M + 1)]
dp[M][K] = 0
ans = 0
for _ in range(N):
a, b = map(int, sys.stdin.readline().split(" "))
for i in range(M + 1):
for j in range(K + 1):
if dp[i][j] != -1 and i - a >= 0 and j - b >= 0:
dp[i - a][j - b] = max(dp[i - a][j - b], dp[i][j] + 1)
ans = max(ans, dp[i - a][j - b])
print(ans)