[코딩테스트] 10. 배낭 문제

배낭 문제(Knapsack)는 DP의 대표 유형이다. N개의 물건 중 무게 제한을 지키면서 가치 합을 최대화한다. 조합 최적화 문제에서 반복적으로 등장하는 패턴이다.

문제 설명

물건이 4개 있고, 배낭 용량은 7이다.

물건	무게	가치
A	1	1
B	3	4
C	4	5
D	5	7

어떤 조합이 최대 가치인지 구해야 한다. 각 물건은 0개 또는 1개만 담을 수 있다 (0/1 배낭).

상태 정의

dp[i][j] = 물건 1~i를 고려했을 때 용량 j로 담을 수 있는 최대 가치

"물건을 하나씩 추가하면서, 각 용량에서의 최적값을 갱신한다"는 구조다.

점화식

물건 i를 담거나 안 담거나 두 가지 경우밖에 없다.

담지 않는 경우 : dp[i][j] = dp[i-1][j]
담는 경우      : dp[i][j] = dp[i-1][j - w[i]] + v[i]   (단, j >= w[i])

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

• dp[i-1][j] : 물건 i 없이 i-1번까지만 고려한 최적값
• dp[i-1][j - w[i]] + v[i] : 물건 i를 담고, 남은 용량 j-w[i]에서의 최적값에 가치를 더함

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= w[i]) {
            dp[i][j] = Math.max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
        }
    }
}

1D로 최적화

2D 배열 대신 1D 배열 하나로 처리할 수 있다. 단, j를 역순(내림차순)으로 순회해야 한다.

int[] dp = new int[W + 1];

for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

왜 역순인가? dp[j - w[i]]를 참조할 때 아직 물건 i가 반영되지 않은 상태여야 하기 때문이다. 오름차순으로 순회하면 dp[j - w[i]]가 이미 물건 i를 담은 상태로 갱신되어, 같은 물건을 중복으로 담는 결과가 나온다.

→ 다음 : 실전 패턴과 면접 대비

---