백준 12865 평범한 배낭

문제 요약

물건의 수 n과 버틸 수 있는 무게 k가 주어진다.
각 물건은 무게 w와 가치 v를 가진다.
배낭에 넣을 수 있는 물건들의 가치의 최댓값은 ?

입력 예시

4 7 (물건의 수 n, 버틸 수 있는 무게 k)
6 13
4 8
3 6
5 12

코드

from sys import stdin
stdin = open("input.txt","r")
input=stdin.readline
n,k=map(int,input().split())
stuff=[[0,0]]
for _ in range(n):
    stuff.append(list(map(int,input().split())))
   
dp=[0]*(k+1)
for i in range(n+1):
    tmp_w=stuff[i][0]
    tmp_v=stuff[i][1]
    for j in range(k,-1,-1):
        if tmp_w<=j:
            dp[j]=max(dp[j],tmp_v+dp[j-tmp_w])

print(dp[k])