BOJ 12865 평범한배낭

Knapsack Algorithm

전형적인 배낭 알고리즘 문제. 담을 수 있는 무게가 정해져있을 때 담긴 물건의 가치 합을 최대로 하는 알고리즘이다.

구조화

dp 배열에 무엇을 메모이제이션으로 기록해야 하는지 생각해보면 어렵지 않게 풀 수 있다. dp[i][j]에 메모해야 할 것은 i번째 물건까지 고려하고 무게가 j 이하일 때 최대 가치 이다.

디폴트

따라서 dp 배열의 업데이트는 다음 식으로 시작한다.

dp[i][j] = dp[i-1][j]

이는 i번째 물건까지 고려하고 무게가 j 이하일 때 최대 가치 는 (i-1)번째 물건까지 고려하고 무게가 j 이하일 때 최대 가치 보다 크거나 같을 것이기 때문이다.

업데이트

i번째 물건의 무게를 w라 하자. dp[i][j]는 가방에 최대로 담을 수 있는 무게가 j인 상황을 가리키므로 w <= j인 경우에만 업데이트를 고려한다.

업데이트의 방향성은 i번째 물건을 아직 고려하지 않았을 때, 즉 (i-1)번째 물건까지 고려했을 때, 최대로 담을 수 있는 무게가 (j-w)일 때 를 봐야 한다.

만약 i번째 물건의 가치(v)를 dp[i-1][j-w]에 더한 값이 dp[i][j]보다 크다면(현재 이 값은 dp[i-1][j]의 값과 일치한다) 값을 업데이트한다.

if w <= j:
    dp[i][j] = max(v + dp[i-1][j-w], dp[i][j])

점화식

위 내용을 정리해서 점화식은 다음과 같이 쓸 수 있다.

dp[i][j] = dp[i-1][j]
if w <= j:
    dp[i][j] = max(v + dp[i-1][j-w], dp[i][j])

직관적으로는 다음과 같이 정리할 수 있다.

물건을 가방에 넣을 수 있을 때(if w <= j), 현재 고려하는 물건을 가방에 넣을 때 가질 수 있는 최대 가치와 (v + dp[i-1][j-w]) 가방에 넣지 않을 때 가질 수 있는 최대 가치를 (dp[i-1][j]) 비교한다.

코드

import sys

input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = map(int, input().split())
        for j in range(1, K + 1):
            dp[i][j] = dp[i - 1][j]
            if w <= j:
                dp[i][j] = max(v + dp[i - 1][j - w], dp[i][j])
    print(dp[N][K])


if __name__ == '__main__':
    main()