알고리즘 유형 : DP, 냅색
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/12865
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
obj = [[0,0]] + [tuple(map(int, input().split())) for i in range(N)]
# knapsack[row][col]는 1, 2, 3, ..., row 번째 물건 총 row개의 물건으로 한도 무게 col인 배낭을 채울 때 최대 가치
# 행 N+1, 열 K+1인 이유는 열은 인덱스가 곧 weight를 의미하도록 의도한 것이고, 행도 첫 번째 물건으로 for를 돌 때,
# 첫 번째 물건을 넣지 않는 경우를 계산할 때 그 이전의 행을 인덱싱하는 구문을 사용할 것이므로, 첫 번째 물건
# 에 해당하는 행 이전에, 값이 모두 0인 하나의 행을 더 넣어준 것이다.
knapsack = [[0]*(K+1) for _ in range(N+1)]
for row in range(1, N+1):
for col in range(1, K+1):
weight = obj[row][0]
value = obj[row][1]
if weight > col:
knapsack[row][col] = knapsack[row-1][col]
else:
knapsack[row][col] = max(knapsack[row-1][col], value + knapsack[row-1][col - weight])
print(knapsack[N][K])풀이 요약
| 행:물건 열:배낭 남은 무게 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| (6, 13) | 0 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| (4, 8) | 0 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| (3, 6) | 0 | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
| (5, 12) | 0 | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
-
핵심 원리는 행을 돌면서 물건 1행꺼 총 1개, 물건 1, 2행꺼 총 2개, 물건 1, 2, 3행꺼 총 3개... 이런 식으로 몇 개의 물건을 가지고 배낭이 1부터 K까지, 모든 남은 무게 상태에서의 최대 가치를 구하는 것이다.
-
어떤 임의의 행 row에서, 배낭의 남은 무게 col에 대해 knapsack[row][col]은 1행에 해당하는 물건, 2행에 해당하는 물건, ..., row에 해당하는 물건, 총 row개의 물건으로 col만큼의 무게를 넣을 수 있는 배낭을 최대 가치로 채우는 경우의 수를 의미한다.
-
이 때, knapsack[row][col]의 값은 현재 행에 해당하는 물건을 넣느냐, 안넣느냐 두 가지 경우 중 최대이다.
1) row 물건을 넣는 경우에는, 현재 물건을 넣고, 배낭 무게에 현재 물건 무게를 뺀 (col - weight) 만큼의 무게를, row 물건 이전의 모든 물건으로 최대 가치로 채우는 경우의 수를 더해준 값이 냅색 값이다.
knapsack[row][col](후보1) = row물건의 가치 + knapsack[row-1][col - row물건의 무게]
2) row 물건을 넣지 않는 경우에는, row 이전의 물건, 즉 1, 2, ..., row-1행에 해당하는 물건 모두를 활용하여 한도 무게 col인 배낭을 최대 가치로 채우는 경우가 냅색 값이다.
이 둘 중 최대인 값을 취하면 된다. (value = 현재 row 행에 해당하는 물건 가치, weight = row물건 무게)
knapsack[row][col](후보2) = knapsack[row-1][col]
3) 이 때, col(배낭 한도 무게)이 현재 행에 해당하는 물건의 무게보다 작은 경우, 현재 물건을 넣을 수가 없으므로, 이 경우 냅색 값은 row물건 그 이전의 모든 물건으로 한도 무게 col인 배낭을 최대 가치로 채우는 게 답이 된다.
knapsack[row][col] = knapsack[row-1][col]
4) 한 가지 의문이 들 수 있는 점은, 어떤 임의의 행 row를 채울 때, row+1에 해당하는 물건을 넣는 건 왜 고려되지 않아도 되는가?이다.
이는 row+1행을 채울 때 row+1행에 해당하는 물건을 넣는 경우가 모든 배낭 한도 무게 col에 대해 계산이 되므로, row행에서는 row물건을 넣을 때와, 넣지 않았을 때 그 이전의 row-1까지의 물건들로만 배낭을 채우는 것을 고려하면 되는 것이다.
배운 점, 부족했던 점
-
여러가지 메모이제이션 활용 형태, 부분 문제 정의를 고민해보면서 물건을 넣을 때마다 배낭의 남은 무게가 달라지므로, 여러가지 온갖 시도해보면서 그걸 고려해서 규칙을 찾고 점화식을 찾아야겠다는 생각은 들었는데, 전체 문제를 "현재 행까지의 모든 물건으로 배낭 한도 무게를 채울 때 최대 가치"로 설정, 즉 넣을 물건을 하나하나 늘려가면서 현재 행에 해당하는 물건을 넣냐, 안 넣고 이 전의 모든 물건들로 채우냐라는 아이디어를 떠올리질 못했다. 아주 어렵고 야무진 문제였다...
-
부분 문제 정의, 점화식, 메모이제이션 활용 형태, 모든 면에서 부족했다. 다행히 구현 자체는 아주 쉬웠다. 아이디어가 핵심인 것 같다.
