평범한 배낭 - 12865번

동적계획법으로 해결할 수 있는 문제이다.

배낭에 담을 물건을 쪼깨어 일부분만 담을 수 있다면 그리디로 풀 수 있지만,

그렇지 않기 때문에 동적계획법을 써줬다.

만약 가방의 무게가 20이고, 들어갈 수 있는 물건 5개가 다음과 같다면,

무게, 가치

2 3

3 4

4 8

5 8

9 10

동적계획법의 표현결과는 다음과 같다.

 

 

n,k = map(int,input().split())
jewels=[[0,0]]
for i in range(n):
    inn = list(map(int,input().split()))
    jewels.append(inn)

dp = [[0]*(k+1) for i in range(n+1)]
for gem in range(1, n+1):
    for bag_weight in range(1, k+1):
        if bag_weight >= jewels[gem][0]:
            dp[gem][bag_weight] = max(dp[gem-1][bag_weight], jewels[gem][1] + dp[gem-1][bag_weight-jewels[gem][0]])
        else:
            dp[gem][bag_weight] = dp[gem-1][bag_weight]
print(dp[n][k])