DP 복원 계획

DP 압축 복원 기준

값만 맞추는 풀이와 선택 경로까지 반환하는 풀이는 같은 전이식이라도 저장해야 할 정보가 다릅니다.

capacity 5
weights 2, 1, 3, 2
values 12, 10, 20, 15
expected 37, items 0, 1, 3
값 전용

압축해도 되는 경우

상태

dp[c] 한 줄만 유지하고 용량을 큰 값에서 작은 값으로 갱신한다.

검증

2차원 기준 구현의 최댓값과 압축 결과가 같은지만 비교한다.

DP 압축 복원 한계

어떤 아이템이 값을 만들었는지 행 정보가 사라져 복원이 어렵다.

경로 포함

압축을 늦추거나 기록을 남길 경우

상태

take[i][c] 또는 parent 기록으로 선택 원인을 보존한다.

복원

마지막 상태에서 시작해 선택된 아이템의 무게만큼 용량을 줄인다.

비용

메모리는 늘지만 동점 처리와 경로 검증을 명확히 남길 수 있다.

1

기준표 작성

2차원 dp와 take로 정답값과 경로를 먼저 고정한다.

2

값 비교

같은 입력에서 best2d == best1d를 확인한 뒤 압축한다.

3

경로 요구 확인

반환 타입이 목록이면 값 전용 배열만 남기지 않는다.

4

동점 규칙 기록

같은 최댓값에서 앞 인덱스 우선인지, 선택 수 최소인지 고정한다.