[BOJ] 평범한 배낭
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 이 클 때에만 그 뒤 검색을 개시한다.
Author And Source
이 문제에 관하여([BOJ] 평범한 배낭), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jujube0/BOJ-평범한-배낭저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)