[알고리즘] 백준 12865 평범한 배낭 / python

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

12865번: 평범한 배낭

 

전형적인 DP문제!

이해하느라 애먹었다 ㅠ

D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치

점화식으로 표현하면, 

D[i][j] = D[i - 1][j]  ( j < w )
D[i][j] = max( D[i - 1][j], D[i - 1][j - w] + v )  ( j >= w)

표에 있는 무게 j가 w보다 작다면, w를 담을 수 없다! 전의 값을 그대로 복사한다

j가 w를 감당할 수 있는 무게면, max값을 찾는다

D[i - 1][j - w]는 w + ❔ = j 에서 ❔다!

여기에 v를 더해주면? w의 가치와 ❔의 가치를 더해주는것

이 값과 j의 이전 값과 비교해서 max값으로!!!

 

n, k = map(int, input().split(' '))
_map = [ [0]*(k+1) for _ in range(n+1) ]

for i in range(1, n+1):
    w, v = map(int, input().split(' '))
    for j in range(1, k+1):
        if j < w:
            _map[i][j] = _map[i-1][j]
        else:
            _map[i][j] = max(_map[i-1][j], _map[i-1][j-w] + v)
            
print(_map[n][k])