백준 12865번 : 평범한 배낭

# N: 물건의 수, K: 최대 무게 W: 무게, V: 가치
N = 0
K = 0
W = [0]
V = [0]

def dp():
    for limit in range(1,K+1):
        for row in range(1,N+1):
            # 1. 담을 수 없는 경우
            if W[row] > limit:
                DP[row][limit] = DP[row-1][limit]
            # 2. 담을 수 있는 경우
            else:
                DP[row][limit] = max(DP[row-1][limit-W[row]] + V[row], DP[row-1][limit])

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

for i in range(N):
    a,b= map(int, input().split())
    W.append(a)
    V.append(b)


DP = [[0 for col in range(K+1)] for row in range(N+1)]



dp()

print(DP)

print(DP[N][K])