배낭 문제(냅색) 시리즈 - BOJ 12865 평범한 배낭, BOJ 12920 평범한 배낭2, Algospot SUSHI

배낭 문제(냅색) 시리즈 - BOJ 12865 평범한 배낭, BOJ 12920 평범한 배낭2, Algospot SUSHI

[분류 : 다이나믹 프로그래밍]

 

  냅색 문제들을 모아 풀이를 공유하는 포스팅입니다. 이 포스팅은 희한한 냅색 문제들 보는 대로 갱신됩니다.

 

1. BOJ 12865 평범한 배낭

  일반적으로 알고있는 냅색을 사용하면 된다. 시간 복잡도는 O(NK)가 된다. 재귀적으로 처리해도 좋고, 일차원 배열을 만들어서 큰 값에서 작은 값으로 내려가면서 데이터 오염을 피하며 dp를 구성해도 좋다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 100;
int N, dp[MAX_N][100001], w[MAX_N], v[MAX_N];
int rec(int p, int k) {
    if (p == N) return 0;
    int& ret = dp[p][k];
    if (ret != -1) return ret;
    ret = 0;
    if (w[p] <= k)
        ret = rec(p + 1, k - w[p]) + v[p];
    ret = max(ret, rec(p + 1, k));
    return ret;
}
int main() {
    memset(dp, -1, sizeof dp);
    int K, i;
    scanf("%d%d", &N, &K);
    for (i = 0; i<N; i++) scanf("%d%d", &w[i], &v[i]);
    printf("%d", rec(0, K));
    return 0;
}

---

2. BOJ 12920 평범한 배낭2

  각 물건이 K만큼 있고 이 K를 위의 평범한 배낭처럼 하나의 아이템으로 보면 최대 1000 x 1000개수로 올라갈 수 있으므로 시간초과와 메모리초과를 면치 못하게 된다.

  [이진수] K를 작은 단위로 쪼갠 이진수의 합으로 생각해보자. 가령 5라면 2^0, 2^1, 2^1으로 분리할 수 있다. 8이라면 2^0, 2^1, 2^2, 2^0으로 분리할 수 있다. 이렇게 이진수 작은 단위의 묶음으로 물건 새로 만들고 냅색을 돌리면 된다. 이진수 작은 단위로 쪼갰기때문에 모든 경우의 수를 다룰 수 있을 뿐더러 K는 최대 10^4이기 때문에 최대 14개의 이진수 묶음이 존재할 수 있고 N개의 물건이 최대 14 * N이 될 수 있고 O(14*N*M)은 충분히 시간 내에 수행될 수 있음을 알 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 1500, MAX_M = 1e4;
int main() {
    int N, M, V[MAX_N], C[MAX_N], i, j, v, c, k, p = 0, cnt, dp[MAX_M + 1] = { 0 };
    scanf("%d%d", &N, &M);
    for (i = 0; i < N; i++) {
        scanf("%d%d%d", &v, &c, &k);
        for (j = 0; k > 0; j++) {
            cnt = min(1 << j, k);
            V[p] = cnt * v;
            C[p++] = cnt * c;
            k -= cnt;
        }
    }
    N = p;
    for (i = 0; i < N; i++) {
        for (j = M; j; j--)
            if (V[i] <= j)
                dp[j] = max(dp[j], dp[j - V[i]] + C[i]);
    }
    printf("%d", dp[M]);
    return 0;
}

---

3. Algospot SUSHI

  지금까지 보던 냅색과 전혀 다릅니다. 딱봐도 O(NM)으로 처리할 수 없습니다.

  [DAG 구성, 슬라이딩 윈도우] 현재 예산 p까지 쓸 수 있고, N개의 초밥이 있을 때 상태를 생각해봅시다. i번째를 초밥을 구매했다고 하면 부분 문제를 가져올 때 dp[p-가격[i]] + 선호도[i]로 표시할 수 있습니다. 여기서 데이터를 가져오는 부분을 모두 일일히 선분으로 그려본다면 DAG가 구성될테고 이는 최소 p-20000부터 p-100까지 부분문제로 두고 데이터를 가져올 가능성있습니다. 즉, p-20001이하부터는 필요가 없다는거죠. 따라서 크기 20000인 window를 두고 슬라이딩 윈도우를 진행해주면 됩니다.

  [최적화] 여기서 가격은 100으로 반드시 나눠떨어지므로 100으로 나눠줍니다. 마찬가지로 예산도 100으로 나눈 나머지는 의미가 없으므로 100으로 나눠줍니다.

  [시간 복잡도] 예산을 하나씩 올려가며 가능한 모든 경우에 대해 부분 문제를 갱신해주면 됩니다. O(NM)은 최대 429,496,720까지 올라가므로 아슬아슬하게 시간 내에 수행됩니다.

#include<algorithm>
using namespace std;
const int MAX_N = 100;
int main() {
    int c, n, m, i, j, dp[201], p[MAX_N], cost[MAX_N], ans, ca;
    scanf("%d", &c);
    while (c--) {
        scanf("%d%d", &n, &m);
        m /= 100;
        for (i = 0; i < n; i++) {
            scanf("%d%d", &cost[i], &p[i]);
            cost[i] /= 100;
        }
        ans = 0;
        memset(dp, 0, sizeof dp);
        for (i = 1; i <= m; i++) {
            ca = 0;
            for (j = 0; j < n; j++) if (i >= cost[j])
                ca = max(ca, dp[(i - cost[j]) % 201] + p[j]);
            dp[i % 201] = ca;
            ans = max(ans, ca);
        }
        printf("%d\n", ans);
    }
    return 0;
}