[백준] 12865번 평범한 배낭

백준_12865

무게와 가치, 2개의 변수를 고려해야하는 2차원 DP문제다
무게를 1~K까지 만들고, N개의 물건으로 해당 무게를 채울 수 있는지 없는지를 확인하고, 채울 수 있다면 만들 수 있는 가치 중 최대값을 가져오면 된다

n, k = map(int, input().split())
stuff = [[0,0]]
dp = [[0]*(k+1) for _ in range(n+1)]
for _ in range(n):
    stuff.append(list(map(int, input().split())))

for i in range(1,n+1):
    for j in range(1,k+1):
        w, v = stuff[i]

        #채우려는 무게 < 물건의 무게
        #물건을 넣을 수 없으므로, 무게가 동일한 이전 가치로 대체한다
        if j < w:
            dp[i][j] = dp[i-1][j]
        #채우려는 무게 >= 물건의 무게
        #물건을 넣을 수 있으므로, 무게가 동일한 이전 가치 & 현재 무게를 넣기 이전 가치+현재 가치 를 비교한다
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)

print(dp[n][k])