12865

오답 여부: o

편집 시간: 2022년 2월 24일 오후 2:29

코드

dp로 풀 수 있다.

f(i, w): 0번째부터 i번째까지 물건들 중에서 w까지 담을 수 있는 가방이 있을 때, 담을 수 있는 최대 가치

f(i, w) = max( f(i - 1, w - weight[i]) + value[i], f(i - 1, w) )

하지만 재귀를 이용한 탑다운으로 풀다보니 엄청나게 느린 결과가 나왔다.

재귀를 쓰지않고 바텀업으로으로 푸니 빠른 결과가 나왔다.