[BOJ] 평범한 배낭

12865 : 평범한 배낭 골드 5

from collections import deque
import sys
input = sys.stdin.readline

nproduct, maxweight = list(map(int, input().split()))

product = []
for _ in range(nproduct):
    w, v = (list(map(int, input().split()))) # weight, value
    if w <= maxweight:
        product.append((w,v))

product.sort(key = lambda x : -x[0])

maxvalue = 0

maxvalueperweight = [-1]*(maxweight+1)
maxvalueperweight[0] = 0

v = set()
v.add(0)

# print(product)
for i in range(len(product)):
    new = set()
    for cw in v:
        cv = maxvalueperweight[cw]
        if cw + product[i][0] <= maxweight and cv + product[i][1] > maxvalueperweight[cw+product[i][0]]:
            new.add((cw+product[i][0], cv + product[i][1]))
            # maxvalueperweight[cw+product[i][0]] = cv + product[i][1]
    for cw, cv in new:
        maxvalueperweight[cw] = cv
        v.add(cw)
print(max(maxvalueperweight))

DP 문제

maxvalueperweight 각 weight 조건에 맞는 maxvalue 를 저장한다.

maxvalueperweight 의 value 보다 weight 이 클 때에만 그 뒤 검색을 개시한다.