[백준][동적 계획법1] 12865. 평범한 배낭 (파이썬/Python)
n, k = map(int, input().split()) wv = [[0,0]] dp = [[0]*(k+1) for _ in range(n+1)] for i in range(n): wv.append(list(map(int, input().split()))) for i in range(1, n+1): for j in range(1, k+1): w = wv[i][0] v = wv[i][1] 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])