1. 문제

12865번

2. 풀이

• 짐을 쪼갤 수 없는 배낭문제 0/1 Knapsack 문제이다.

• 짐의 번호 i와 배낭에 들어있는 짐의 무게 j를 인덱스로 갖는 메모이제이션 공간을 통해 문제를 전개한다.

• i / j	0	1	2	3	4	5	6	7
  0	0	0	0	0	0	0	13	13
  1	0	0	0	0	8	8	13	13
  2	0	0	0	6	8	8	13	14
  3	0	0	0	6	8	12	13	14

• 위의 표에서 column은 가방의 무게이다. 즉, j = 1일 때 1만큼 무게를 갖도록 짐을 넣을 때 최대 가치 V의 합을 표에 적은 것이다. 물론 j = 0, 1, 2 일때 집어넣을 수 있는 짐이 없으므로 가치는 0이다.

• j=3 일 때, 2번째 짐(i = 2)을 집어 넣을 수 있으므로 6을 적는다.

• i = 3, j = 3 칸에 6을 적은 이유는 'i = 3 까지 탐색했을 때 최대값이 6이다.' 라는 의미이다.

• j = 4 일 때, i = 0의 짐 무게는 6으로 넣을 수 없다. i = 1에서는 짐의 무게가 4이므로 해당 짐을 집어넣을 수 있다. i = 2의 짐을 넣을 수 있으나 가치가 더 낮으므로 넣지 않는다.

• j = 7 일 때부터 2개 이상의 짐을 넣을 수 있다. i = 0에서 V가 13이며 일단 넣는다. i = 1에서는 짐의 무게 4이므로 가방에 들어있는 짐의 무게가 3인 상태에 추가할 수 있다. 이때 i = 0과 그 가치를 비교한다. 즉, (무게 6 : i = 0 가치)와 (무게 3인 가방의 가치 + 무게 4 : i = 1 가치)을 비교하는 것이다. 무게 3인 상태의 가방의 가치는 위 표에서 i = 1, j = 3의 값을 가져오는데 그 값이 0 이다. 따라서 13 > 8 + 0 이므로 j = 7일 때 i = 1까지 최대값은 13이다.

  dp[i = 0][j = 7] > dp[i = 0][j = 7 - W[i = 1]] + V[i = 1]
  이때, dp는 2차원 메모이제이션 공간이며, W는 i번째 무게, V는 i번째 가치이다.

N, K = map(int, input().split())

W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[0 for _ in range(K+1)] for _ in range(N)]

for i in range(N):
    for j in range(K+1):
        if j < W[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + V[i])

print(dp[N-1][K])

3. Reference

https://st-lab.tistory.com/141

• Knapsack이라는 낯선 문제를 접했다. '무게'라는 아날로그 개념을 동적계획법을 위한 메모이제이션 공간의 index로 사용할 수 있다는 것에서 매우 신선한 문제였다.
• 알고리즘 분야는 모르는 것이 참 많고 접근법을 모르는 상태에서 맨땅에 헤딩하는 것은 불가능에 가까운 듯 하다. 그러니 지속적으로 도전하는 수 밖에는 없다. 당장은 몰라도 3 ~ 5년 후엔 빛을 볼 것이라 믿는다.