풀이
NP-Hard 문제 중 하나인 냅색 문제(knapsack problem)입니다. 물품을 순서대로 보면서 넣을지 말지 결정하는데, 넣으려면 당연히 가방의 남은 용량이 이 물품의 무게 이상이어야 합니다.
knapsack(itemNum, limit)은 itemNum번보다 이전의 물품은 다 고려한 상태에, 현재 가방에 남은 용량이 limit일 때 앞으로 itemNum~N번 물품을 넣으면서 얻을 수 있는 최대 가치 합입니다. 매 문제는 이번 물품을 넣을지 말지만 결정하면 되므로 총 O(NV)의 시간에 풀 수 있습니다.
w,v 값을 이용해야하므로 2차원 배열을 이용한다.
dp[i-1][j-w]+v : w,v 물건을 넣는 경우
dp[i-1][j] : 물건을 넣지 않는 경우
코드
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
bag = [[0,0]]
for i in range(n):
bag.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): # 버틸 수 있는 무게
w = bag[i][0] # 물건 무게
v = bag[i][1] # 가치
if w > j: # 물건을 넣지 않는 경우 ( 물건 무게 > 버틸 수 있는 무게)
dp[i][j] = dp[i-1][j]
else :
dp[i][j] = max(dp[i-1][j-w]+v,dp[i-1][j])
print(dp[n][k])
