140. 12865(평범한 배낭)

import sys
input = sys.stdin.readline

N,K = map(int, input().split())
# K => 무게

DP = [[0]*(K+1) for _ in range(N+1)]


for i in range(1,N+1):
    weight, value = map(int, input().split())
    for j in range(1,K+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])

문제요약

군대가기전 여행가는 준서의 배낭을 최대한 가치있게 준비할 수 있도록 하자. 

설명

첫줄에 K는 무게이다.

두번째 줄 부터 첫번째 인덱스 값이 무게이다.

 

무게 0~K까지 증가시키면서 두번째 줄부터 들어오는 물건의 무게와 가치를 비교한다.

DP i 인덱스의 0~K 무게(j) 는 각 무게에서 가장 높은 가치를 지닌 것이라고 생각하면 된다.

 

전의 무게와 , 현재 새로 갱신하는 무게를 비교해 보았을 때 더 큰 무게를 저장하면된다.

 

다음 과 같이 입력이 4 8일때 최대 4kg를 지닐 수 있다면 8의 가치가 최대이다.

하지만 최대 지닐 수 있는 무게가 6kg 일 때 4kg을 지니고 가는 것 보다는 6kg을 지니고 가는게 더 가치가 높다.

 

따라서 

DP[i][j] = max(value + DP[i-1][j-weight], DP[i-1][j])

다음과 같이 새로 갱신하는 무게와 전의 무게중 더 큰 것을 비교해서 저장하면 된다.

현재 j무게에서 weigth을 빼주는 이유는 , value를 더하게 된다면 남은 j-weight만큼 무게가 남을 것이고, 그 인덱스에 해당하는 무게를 더해주어 무게를 가지고 계산할 수 있는 가장 큰 값을 만들 수 있다.

위 공식으로 DP[전 인덱스][남은 무게의 값]의 가치와 현재 가치를 더해 최대 가치를 만들 수 있다.