[dp/백준] 12865번: 평범한 배낭

-문제: https://www.acmicpc.net/problem/12865

 

-정답풀이: 

풀이 방법 익혀야겠다

dp의 열이 k까지 있으므로 j가 반복문을 돌면서, 가방의 크기가 점점 커지고 있고, 거기에 물건을 넣는 거라고 생각하면 될 것 같다 

 

if j < weight[i] (가방이 현재 담을 수 있는 무게(j)가 물건의 무게보다 적은경우)

위 상황에서는 물건을 가방에 넣을 수 있는 상황이 아니므로 이전 물건의 같은 무게 값을 누적한다 

 

if j >= weight[i] (가방이 현재 담을 수 있는 무게가 물건의 무게보다 큰 경우)

이 상황에서는 현재 물건을 담을 수 있다. 근데 가치를 최대로 해야하기 때문에 

max(이전물건, 같은무게 / 이전물건+(현재 물건 넣기 전 무게)의 가치에 현재 물건의 가치)를 계산한다 

n,k=map(int,input().split())
weight=[0]
value=[0]
for _ in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
    
dp=[[0]*(k+1) for _ in range(n+1)]

for i in range(1,n+1): #i가 현재 물건
    for j in range(1,k+1): #j가 현재의 무게
        if j >= weight[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][k])