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

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

12865번: 평범한 배낭

# 문제 설명

첫 줄 : 물품의 수 N(1 ≤ N ≤ 100), 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)

두번째 줄~N개의 줄 : 물건의 무게 W(1 ≤ W ≤ 100,000), 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

 

배낳에 넣을 수 있는 물건들의 가치의 최댓값 구하기

 

# 해결 방법

 

 

 

 

 

dp 는 N(1~N)번째 물건을 넣을 때 버틸 수 있는 무게를 1~K까지 조절하여 계산한다.

 

 

 

 

 

예를 들어 2번째 물건을 넣을 때 

K가 2번째 물건의 무게인 4가 되기전까지는 그전 물건인 1번째 물건을 넣을 때의 가치를 넣는다.

K가 4가되어 2번째 물건을 넣을 수 있게 되면 

2번째 물건을 넣지 않았을 때 (1번째 물건을 넣었을 때) 의 가치와

2번째 물건을 넣고 (남은 무게만큼 1번째 물건을 넣었을 경우)의 가치 중

가장 큰 가치를 dp 에 추가한다.

 

...

이를 반복한다.

 

 

 

# 코드

import sys
input=sys.stdin.readline

n,k=map(int,input().split())

info=[[0,0]]
for _ in range(n):
    info.append(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):
        print(i,j)
        w = info[i][0]
        v = info[i][1]
        if j<w:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)

print(dp[n][k])