[백준][Python] 12865 평범한 배낭

0,1 knapsack 선택하느냐 마느냐의 문제는 greedy가 안되기 때문에 

점화식을 세울 수 있다면 dp 아니면 완탐이다.

K라는 무게값을 1~target값까지 증가시키며 최고 가치를 누적시키면 된다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
wei_cost = [[0,0]]
dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for _ in range(N):
    wei_cost.append(list(map(int, input().split())))


for i in range(1, N + 1):
    for j in range(1, K + 1):
        weight = wei_cost[i][0] 
        cost = wei_cost[i][1]
        if j < weight:
            dp[i][j] = dp[i - 1][j] 
        else:
            dp[i][j] = max(cost + dp[i - 1][j - weight], dp[i - 1][j])

print(dp[N][K])