[Python/백준]12865번_평범한 배낭(DP, 냅색)

 

 

 

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

12865번: 평범한 배낭

 

 

코드 : 

N,K = map(int,input().split())
items = []
dp = [0 for _ in range(K+1)]
for i in range(N):
    w,v = map(int,input().split())
    for j in range(K,w-1,-1):
        dp[j] = max(dp[j],dp[j-w]+v)
print(dp[-1])

 

 

dp[j] : 가방에 j 무게 물건이 있을 때의 가치 

dp[j-w]+v : w 무게만큼의 물건을 넣는다. 

 

 

 

 

 

여기서 주의해야할 점은 물건들이 무한대(?)로 있는 것이 아니라 하나 뿐이라는 것이다. 

즉, for j 를 K에서부터 -1씩 줄여가며 채워야한다.

만약 w에서부터 채운다면 한 물건이 2번 들어가는 경우가 생기기 때문이다. 

 

 

만약 물건이 무한대로 있다면 앞에서부터 채워야한다. 

 

 

 

 

김태원 강의에서는 무한대로 들어갈 수 있는 문제를 풀어서 몇번 틀렸다가 카톡방에 물어보고 겨우 알았다. 

조건을 세세하게 살펴봐야한다.