[파이썬 / 백준 12865번] 평범한 배낭

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

N,K=map(int,input().split())
vl=[[0,0]]
for i in range(N):
    vl.append(list(map(int,input().split())))
dp=[[0 for _ in range(K+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,K+1):
        w=vl[i][0]
        v=vl[i][1]
        if j<w:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(v+dp[i-1][j-w],dp[i-1][j])

print(dp[N][K])

머리를 꽁꽁 싸매고 하다가 결국 풀이를 봤다.

냅색 알고리즘이 또 있는지 몰랐다.

리스트의 인덱스 자체를 무게로 쓸 생각을 못했는데, 알고나니 활용할 일이 많을 것 같다.