[백준] 12865 : 평범한 배낭 python

 

 

[물건의 개수]x[가방에 넣을 수 있는 최대 무게] 크기의 dp행렬을 생성하고 0으로 초기화한다.

물건을 하나씩 보면서, 현재 물건을 넣을 수 없다면 기존의 가치값을 그대로 가져오고

넣을 수 있다면 기존의 가치와 현재 물건을 넣을 수 있는 시점에서의 가치 + 현재 물건의 가치 중 큰 값을 저장한다.

 

n,k = map(int,input().split())
item = [[0]*2 for _ in range(n+1)]
for i in range(1,n+1):
    item[i] = list(map(int,input().split()))

dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,k+1):
        weight = item[i][0]
        value = item[i][1]
        # 물건을 담을 수 없다면 기존의 가치를 그대로 가져옴
        if j<weight:
            dp[i][j] = dp[i-1][j]
        # 물건을 담을 수 있다면
        # 기존의 가치와 현재 물건이 들어갈 수 있는 시점의 가치 + 현재 물건의 가치
        # 중에서 더 큰 것으로 갱신함
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight]+value)
        
print(dp[n][k])