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

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

12865번: 평범한 배낭

맨처음에는 정렬을 하고, 그리디로 풀려고 했는데, 잘 안풀렸다....

고민을 하다 결국에는 다른 분 풀이를 보고 이해했다.

#백준 12865 평범한 배낭

import sys
input=sys.stdin.readline
N,K=map(int,input().split())
lst=[[0,0]]
for _ in range(N):
    W,V=map(int,input().split())
    lst.append([W,V])
dp=[[0]*(K+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,K+1):
        weight=lst[i][0]
        value=lst[i][1]
        if j<weight:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(value+dp[i-1][j-weight],dp[i-1][j])

print(dp[N][K])

각 물건에 대해서

임의의 최대 무게(j)보다 작으면, 그 위의 행의 값을 가져오고,

임의의 최대 무게(j)보다 크거나 같다면, 위의 행의 값과 value+dp[i-1][j-weight]의 값을 비교하여 큰 값을 저장한다.

 

열심히하자..