[백준 - 12865] 평범한 배낭

dp[weight]를 현재 무게 한도에서 얻을 수 있는 최대 가치로 뒀다. 물건 하나를 볼 때마다 넣지 않는 경우와 넣는 경우를 비교한다.

dp[w] = max(dp[w], dp[w - itemWeight] + itemValue)

여기서 무게를 큰 쪽부터 내려오며 갱신했다. 앞에서부터 갱신하면 같은 물건을 이번 차례에 여러 번 사용한 값이 다시 참조될 수 있다. 역순 순회는 2차원 DP를 1차원으로 줄이면서도 0/1 조건을 지키기 위한 장치였다.

문제: 12865 평범한 배낭 · 코드: GitHub에서 보기