공간을 최적화한 배낭

전체 표는 n 곱하기 cap만큼의 메모리를 사용하므로 큰 입력에서는 문제가 될 수 있습니다. 공간 최적화를 사용하면 이를 재사용하는 한 행으로 줄일 수 있습니다.

각 칸이 이전 행만 읽고 그보다 오래된 행은 전혀 읽지 않는다는 점에 주목하세요. 따라서 전체 격자를 한 번에 저장할 필요가 없습니다.

길이가 cap+1인 dp 배열 하나만 유지합니다. 각 물건을 처리할 때 새 행을 나타내도록 배열을 제자리에서 덮어씁니다.

용량을 왼쪽에서 오른쪽으로 순회하면 dp[w - wt[i]]가 이미 같은 물건에 대해 갱신되었을 수 있습니다. 그러면 물건 i를 두 번 선택하게 됩니다.

해결 방법은 용량을 큰 값에서 작은 값으로 반복하는 것입니다. 역순으로 진행하면 dp[w - wt[i]]가 여전히 이전 물건까지의 값을 담고 있음이 보장됩니다.

dp[w]를 계산할 때 더 작은 인덱스인 w - wt[i]는 이번 순회에서 아직 변경되지 않았으므로, 의도한 대로 바로 위 행을 반영합니다.

wt[i]보다 작은 용량에는 물건을 담을 수 없으므로 반복문을 wt[i]에서 멈춥니다. 이 용량들을 건너뛰면 의미 없는 반복을 줄일 수 있습니다.

전체 해법은 배열 하나를 사용하는 중첩 반복문 두 개입니다. 바깥쪽은 물건, 안쪽은 용량을 역순으로 순회하면 정답을 얻을 수 있습니다.

모든 물건을 처리한 뒤 dp[cap]에 최댓값이 저장됩니다. 이는 2차원 표에서 얻는 값과 같지만 메모리는 훨씬 적게 사용합니다.

알고리즘의 속도가 빨라진 것은 아닙니다. 여전히 n 곱하기 cap만큼 계산합니다. 단지 메모리 사용량을 이차에서 선형으로 줄였을 뿐입니다.

cap이 크고 2차원 격자가 메모리 제한을 초과할 때 이 기법이 문제를 해결해 줍니다. 기억해 둘 가치가 있는 경연 필수 기법입니다.

1차원 배낭 문제의 핵심 규칙을 확인해 보세요.

2차원 표를 배열 하나로 합치고, 올바른 계산을 위해 용량을 역순으로 순회했습니다. 이로써 이차 메모리를 선형 메모리로 바꾸었습니다. 🚀