백준12865: 평범한 배낭 - DP, knapsack(Python, 파이썬)

냅색이 실타.

코드출처

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
# 물건 수, 무게
dp = [0] * (K+1)

for _ in range(N):
    w, v = map(int, input().split()))
	  if w > K:
      	# 만약 물건의 무개가 이미 최대치를 넘었다면
		  continue
    for j in range(K, 0, -1):
        if j + w <= K and dp[j] != 0:
            dp[j+w] = max(dp[j+w], dp[j]+ v)
    dp[w] = max(dp[w], v)

print(max(dp))