12865번: 평범한 배낭 (DP) - Fastcampus

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

# dp[i][j] = 배낭에 넣을수 있는 물건의 최대값
#            (i번째 물건까지 j사이즈 배낭에 넣을때)
#
# dp[i][j] = max(물건이 안들어갈때의 가치, 물건의 가치 + 남은 공간의 가치)
#          = max(dp[i-1][j], v + dp[i-1][j-w])
#
#     (w, v)   j=1   2   3   4   5   6   7
# i=1 (6, 13)                        13  13
# i=2 (4, 8)                 8   8   13  13
# i=3 (3, 6)             6   8   8   13  14
# i=4 (5, 12)            6   8   12  13  14

def run(N, K, a):
    dp = [[0]*(K+1) for _ in range(N+1)]
    a = [(0, 0)] + a  # dp와 a 인덱스 동일하게 맞추기

    for i in range(1, N+1):
        w, v = a[i]
        for j in range(1, K+1):
            if j < w:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v + dp[i-1][j-w])
                
    return dp[N][K]


N, K = map(int, input().split())
stuff = [tuple(map(int, input().split())) for _ in range(N)]

value = run(N, K, stuff)
print(value)