DP- 0-1 Knapsack (백준 12865 평범한 배낭)

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

12865번: 평범한 배낭

0-1 Knapsack 문제

 

0-1 Knapsack은 물건을 쪼갤 수 없기 때문에 DP로 풀어야 한다.

DP 배열은 DP [N개의 물건까지 확인했을 때][물건의 무게] = 물건의 가치이다.

 

이때, i 번째까지 물건을 확인했을 때, j까지 담을 경우에는

dp [i][j] = max(dp [i][j] = max( dp [i-1][j], dp [i-1][j-item [i][0]] + item [i][1])

dp [i번째까지][j무게까지] = max(안 담고 저번 물건까지 확인한 그대로 갈 경우의 가치, 이번 물건만큼의 무게를 뺐을 때 얻을 수 있는 가치 + 현재 물건의 가치)

 

 

물론 i번째 아이템 무게가 가방 K보다 무거울 경우는 물건을 담을 수 없다( if item [i][0]>j:  dp [i][j] = dp [i-1][j] )

 

 

import sys

n,k = [int(i) for i in sys.stdin.readline().split()]

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

for _ in range(n):
    item.append([int(i) for i in sys.stdin.readline().split()])


for i in range(n):
    for j in range(1,k+1):
        if item[i][0]>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max( dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])



print(dp[-1][-1])