✔ 풀이를 위한 아이디어
- 다이나믹 프로그래밍 (Dynamic Programming)
- 분할 가능하지 않은 배낭 문제 (knapsack 문제)
✔ 알고리즘 설명
야간 근무를 뛰며 고민해봐도 도저히 아이디어가 떠오르지 않아, 알고리즘 자체를 공부하기로 결심하였다. 밑의 그림은 직접 그린 것으로, 주어진 예제를 구하는 과정을 나타내고 있다.
-
(N+1) x (K+1) 사이즈의 2차원 배열을 선언하고, default 값은 모두 0으로 넣어준다. 이때, 빨간색으로 칠한 쪽은 실제로는 사용하지 않는 숫자들이지만 코드의 일반화를 위해 추가로 정의하였다.
-
for문을 N번동안 돌면서 각 물건의 무게와 가치 값을 받는다. 이때 '어떠한 판단'을 하며 차례차례 배열을 채워나간다. (이 부분은 밑에 자세히 설명하겠다.) 좌측의 검은색 글씨로 써있는 숫자는 각 물건의 무게이며, 동그라미 안에 써있는 값은 물건의 가치이다. 편의를 위해 무게가 작은 값부터 들어오는 경우로 가정하였으며, 민트색 -> 파란색 -> 남색 -> 보라색의 순서로 채워나가진다고 보면 된다.
-
N번의 각 케이스에서, 물건의 무게 합이 1일 때부터 K일 때까지 (이 예제에서는 7) 각 무게에서 취할 수 있는 가치의 최대값을 계산한다. 이때, '지금까지 들어온' 물건들에 대해서만 판단한다. (DP)
-
위에서 말한 '어떠한 판단'은 다음과 같다.
Case1: 만약 새로 들어온 물건의 무게가 현재 가용 무게 (1부터 K까지 변하는) 보다 크다면, 그 물건은 넣을 수 없으므로, 위 그림에서의 화살표와 같이 이전까지의 최댓값을 그대로 가져온다.Case2: 물건을 넣을 수 있는 경우라면, 두 값을 비교하여 최대값을 넣어준다.
하나는 자신을 넣지 않은 이전까지의 최대값이고, 나머지 하나는 자신을 넣고 남은 무게를 최대로 활용했을 때의 값이다. 이때 남은 무게를 최대로 활용하는 경우는 이미 계산된 값을 활용한다.
✔ 구현된 코드
import sys
N, K = map(int, sys.stdin.readline().split())
dp = [[0]*(K+1) for _ in range(N+1)]
for i in range(1, N+1):
weight, value = map(int, sys.stdin.readline().split())
for j in range(1, K+1):
if weight > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight]+value)
print(dp[N][K])- 다소 어려운 알고리즘에 비해 코드는 생각보다 간단하다. 위에서 상세하게 설명했기 때문에 추가적인 설명은 하지 않도록 하겠다.
핵심 점화식
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight]+value)
✔ 관련 개념
- 다이나믹 프로그래밍 중 배낭 문제
