12865 평범한 배낭

문제: https://www.acmicpc.net/problem/12865

가장 평범한 냅색 DP 문제, 냅색 DP 문제는 용량 제한이 있는 것과, 현재 어디까지 탐색했는지를 인자로 DP 테이블을 구성하고, 그 다음에 물체를 하나씩 넣었다 빼었다 하는 경우를 체크해보면서 탐색값을 찾는 과정으로 이루어집니다.

i 번재 아이템 까지 고려했을 때, 현재 최대 무게가 j인 경우 최대 가치를 dp[i][j]라 합시다. 이 경우에 각 아이템에 대해 우리가 할 수 있는 선택은 2가지 입니다.

1. dp[i + 1][j] = dp[i][j]
   해당 아이템을 추가 안하기
2. dp[i+1][j] = dp[i][j - weights[i]] + values[i]
   해당 아이템을 추가할 수 있는 경우(j - weights[i] >= 0)

이렇게 해서 dp 테이블을 채울 인덱스는 i는 [1, N+1), j는 [1, K+1) 가 됩니다.

이렇게 해서 구해지는 값 중에 제일 큰 값이 dp[i+1][j] 가 되겠지요. 그리고 초기값은 정의상

for item in range(N+1):
	dp[item][0] = 0
for volume in range(K+1):
	dp[0][volume] = 0

dp[item][0] = 0은 무게 제한이 0일 때 가치도 0, dp[0][volume] = 0은 고려할 아이템이 없을 때 가치도 0임을 의미합니다.

이렇게 해서,dp[N][K] 를 구하면 됩니다. 하향식과 상향식 두 방법의 코드 다 남겨 놓겠습니다. 공통되는 입력부는 앞부분만 두었습니다.

상향식

from sys import stdin


def read():
    return stdin.readline().rstrip()


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

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

weights = [
    0,
]
values = [
    0,
]

for idx in range(N):
    w, v = map(int, read().split())
    weights.append(w)
    values.append(v)

for item in range(1, N + 1):
    for curr_weight in range(1, K + 1):
        w = weights[item]
        v = values[item]

        if curr_weight - w < 0:
            dp[item][curr_weight] = dp[item - 1][curr_weight]
        else:
            dp[item][curr_weight] = max(
                dp[item - 1][curr_weight - w] + v, dp[item - 1][curr_weight]
            )

print(dp[N][K])

하향식(메모이제이션 적용)

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

for idx in range(K + 1):
    dp[0][idx] = 0
for jdx in range(N + 1):
    dp[jdx][0] = 0


def get_sum(n: int, w: int) -> int:
    """현재 가방 제한이 w일 때 n번째 아이템까지 채운 최적의 가치합"""
    if dp[n][w] != -1:
        return dp[n][w]
    if w - weights[n] >= 0:
        dp[n][w] = max(
            get_sum(n - 1, w), get_sum(n - 1, w - weights[n]) + values[n]
        )
    else:
        dp[n][w] = get_sum(n - 1, w)
    return dp[n][w]


print(get_sum(N, K))