백준 12865번: 평범한 배낭 (Python, PyPy3)

접근

대표적인 동적 계획법(Dynamic Programming) 문제 중 Knapsack 문제이다.

일단 (N + 1) * (K + 1) 행렬을 준비하여 문제를 풀게 된다. 행 별로 채워가면서 해당 무게별 채울 수 있는 가장 큰 값을 채워나가기 시작하여 첫 행을 채운다.

무게/가중치	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
6 / 13	0	0	0	0	0	0	13	13
4 / 8
3 / 6
5 / 12

무게가 6이고 가중치가 13인 물건을 가지고 가방을 채운다고 했을 때, 5까지는 6의 무게가 나가는 물건을 넣을 수 없기 때문에 0이며, 6부터는 넣을 수 있으므로 13의 가치를 가지게 된다.

무게/가중치	0	1	2	3	4	5	6	7
0	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
5 / 12

두번째 열을 채울 때 3까지는 4의 무게를 가진 물건을 넣지 못해 0이며, 4부터는 8의 가치를 가진다. 하지만 무게가 6이 되게 되면 13의 가치를 가진 무게 6의 물건을 넣는 것이 최대값이므로 이 값을 넣어준다.

무게/가중치	0	1	2	3	4	5	6	7
0	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

세번째 열을 채울 때 2까지는 0, 3일때는 8, 6일때는 13의 가치를 가지게 되는데, 여기서 무게가 7이 되었을 경우 무게 3인 물건의 가치와 무게 4인 물건의 가치를 더한 14가 최대값이 된다.

이를 점화식으로 표현하면 다음과 같다.

i 번째 아이템까지 사용할 수 있을 때, j의 무게 안에서 구할 수 있는 최대 가치는

1. dp[i - 1][j - weight[i]] + value[i]
2. dp[i - 1][j]

중 더 큰 값을 가지게 된다.

예시로 위의 세번째 열 무게 7일때, 무게가 3이고 가치가 6인 가방을 넣기 위해 dp[i - 1][j - 무게3] = 8에 무게3을 가진 물건의 가치 6을 더해주어 해당 칸에는 14의 값을 가지게 된다.

아이템을 챙기지 않았을 경우엔 단순히 dp[i - 1][j]를 넣어주면 된다.

참고 : [백준알고리즘] 12865번: 평범한 배낭

코드

import sys

n, k = map(int, sys.stdin.readline().split())
wl = [0]
vl = [0]
for _ in range(n):
    w, v = map(int, sys.stdin.readline().split())
    wl.append(w)
    vl.append(v)
dp = [[0 for _ in range(k + 1)] for __ in range(n + 1)]
for i in range(n + 1):
    for j in range(k + 1):
        if j - wl[i] >= 0:
            dp[i][j] = max(dp[i - 1][j - wl[i]] + vl[i], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][k])

Python이 시간 초과하여 PyPy3으로 제출하였다.

더 생각해 볼 것?

특히 이 동적계획법(Dynamic Programming) 파트에 들어서서 새로운 문제를 마주칠 때마다 엄청 헤메고, 몇몇 문제는 자력으로 풀지 못하는 경우가 있었다. 새로운 문제를 마주쳐도 풀 수 있는 실력을 키우면서도 못풀었던 문제를 다시 되새겨 앞으로는 비슷한 문제를 활용할 수 있도록 해야겠다.