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

※ 문제

https://www.acmicpc.net/problem/12865

 

 

※ 문제 유형

다이나믹 프로그래밍, 배낭 문제(GOLD_5)

 

※ 나의 풀이

• • DP를 이용하여 문제 해결
  • 역순으로 DP값을 max로 비교 계산

import sys

N, K = map(int, sys.stdin.readline().split())

dp = [0] * (K + 1)
items = []
for _ in range(N):
    items.append(list(map(int, sys.stdin.readline().split())))


for W, V in items:
    # 역순으로 계산
    for i in range(K, W - 1, -1):
        dp[i] = max(dp[i], dp[i-W] + V)
        
print(dp[K])