배낭 문제의 기본 구조와 최적화 원리

다이나믹 프로그래밍에서 배낭 문제는 상태 전이를 이해하는 데 중요한 예시입니다. 주요 유형은 0/1 배낭, 무한 배낭, 다중 배낭, 분할 배낭 등으로 나뉩니다. 각각의 차이는 선택 가능한 횟수와 제약 조건에 따라 달라집니다.

기본적인 상태 정의

dp[i][j]는 처음 i개의 아이템 중에서 총 용량이 j 이하인 조건에서 얻을 수 있는 최대 가치를 의미합니다. 여기서 중요한 점은 dp[0][0] = 0으로 초기화해야 하며, 이는 아무것도 선택하지 않은 경우를 나타냅니다.

0/1 배낭 문제 (일반적 구현)

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
}

여기서 내부 루프는 역순으로 진행되어, 동일한 아이템이 두 번 이상 사용되는 것을 방지합니다.

무한 배낭 문제 (완전 배낭)

for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= m; j++) {
        f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
}

이 경우는 동일한 아이템을 여러 번 선택할 수 있으므로 순방향 탐색이 가능합니다.

다중 배낭 문제 (제한된 개수)

각 아이템이 최대 s[i]개까지 선택 가능한 경우, 이는 직접적으로 처리하기 어려우므로 이진 분할 최적화가 사용됩니다. 이를 통해 다중 배낭을 0/1 배낭 문제로 변환할 수 있습니다.

// 이진 분할 최적화
int cnt = 0;
for (int i = 1; i <= n; i++) {
    int a = weight[i], b = value[i], s = count[i];
    int k = 1;
    while (k <= s) {
        v[++cnt] = a * k;
        w[cnt] = b * k;
        s -= k;
        k *= 2;
    }
    if (s > 0) {
        v[++cnt] = a * s;
        w[cnt] = b * s;
    }
}
// 이후 0/1 배낭 알고리즘 적용

분할 배낭 문제 (그룹 배낭)

각 그룹에서 하나만 선택할 수 있을 때, 다음과 같이 해결합니다:

for (int i = 1; i <= n; i++) { // 그룹 순회
    for (int j = m; j >= 0; j--) { // 용량 역순
        for (int k = 1; k <= size[i]; k++) { // 그룹 내 항목
            if (j >= weight[i][k]) {
                f[j] = max(f[j], f[j - weight[i][k]] + value[i][k]);
            }
        }
    }
}

이중 용량 배낭 (2차원 배낭)

두 가지 제약 조건(예: 체력과 시간)이 동시에 존재하는 경우, 상태를 세 차원으로 확장합니다.

for (int i = 1; i <= n; i++) {
    for (int j = V; j >= v1[i]; j--) {
        for (int k = W; k >= v2[i]; k--) {
            f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + w[i]);
        }
    }
}

실제 문제 예시: 숫자 조합

주어진 숫자들로 특정 합을 만들 수 있는 경우의 수를 구하는 문제입니다.

int f[M] = {0};
f[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = M; j >= a[i]; j--) {
        f[j] += f[j - a[i]];
    }
}
cout << f[M];

모듈러 연산 활용 (마법 카드 문제)

총 마력 소모량이 특정 값의 배수여야 하는 조건이 있을 때, 모듈러 연산을 통해 상태를 관리합니다.

for (int i = 1; i <= n; i++) {
    for (int j = 0; j < k; j++) {
        dp[i][j] = dp[i-1][j];
        int prev = (j - a[i] % k + k) % k;
        dp[i][j] = max(dp[i][j], dp[i-1][prev] + b[i]);
    }
}

특수 사례: 편의점 문제

예를 들어, "정확히 한 번만 선택" 또는 "최소 3개 이상 선택" 등의 조건이 추가될 수 있으며, 이는 상태 정의를 조정하여 해결합니다.

기억화 검색 (Memoization) 활용

깊이 우선 탐색과 함께 메모이제이션을 사용하면 재귀 구조에서도 효율적인 해결이 가능합니다. 예를 들어, 스키어의 최대 이동 거리를 계산할 때, 각 위치에서 가능한 경로를 미리 저장해둡니다.