BOOKTHIEF 문제 솔루션 질문 있습니다.

  • Elevista
    Elevista

    BOOKTHIEF

    Coders high 2013 이 위키에 나온 상세 솔루션을 보고
    따라하는 중인데요

    설명이 잘 이해가 안가는 부분이 있어서 질문드립니다.

    J. 책도둑

    평범한 0-1냅색이라고 가정하면 다음과 같은 DP식을 세울수있다:

    • D[N, V] := N종류의 아이템에 대해 고려해서, V칸을 채웠을때의 최대 값어치
    • D[N, V] = max\{ D[N-1, V], D[N-1, V-\text{(volume of item)}] + \text{(value of item)} \}

    v_{i} = \text{(volume of item)}, c_{i} = \text{(value of item)}이라고 하고, 아이템의 갯수를 k_{i}라 하자.

    위의 식에서 0-1을 0-k로 확장시킨다는 느낌으로 식을 바꿔 써보면:

    \begin{aligned} D[N, V] = max\{ & D[N-1, V],D[N-1, V-v_{i}]+c_{i},D[N-1, V-v_{i}*2]+c_{i}*2,\\ &..., D[N-1, V-v_{i}*k_{i}]+c_{i}*k_{i} \} \end{aligned}

    묶어서 쓰면 다음처럼 쓸수있다.

    D[N, V] = \max_{x} \{D[N-1, x] + (V-x)/v_{i}*c_{i}\} \\ (단, x \equiv V \bmod v_{i} 이고, V-v_{i}*k_{i}≤ x ≤V이다.)

    x에 대한 식만 남기고 V에 대한 부분은 밖으로 뺄 수있다.

    D[N, V] = \max\{ D[N-1, x]-x/v_{i}*c_{i} \} + V/v_{i}*c_{i}

    f(x) = D[N-1,x]-x/v_{i}*c_{i} 라고 하자.
    그렇다면 D[N, V]를 다음과 같이 구할수 있다.

    1. f(V)값을 PQ에 넣는다.
    2. PQ의 top인 x값이 V와 v_{i} * k_{i}를 넘게 차이나면 top을 제거한다
    3. PQ의 top인 f(x)값에 대해 D[N,V] = f(x) + V/v_{i}*c_{i}이다.

    최대 PQ의 크기는 O(V)이므로, 시간 복잡도는 O(NV lg V)이다.
    이렇게 작성해도 AC를 받기엔 충분한 속도지만, 조금 더 속도 향상을 할 수 있다.
    PQ안에 있는 2개의 t1 < t2에 대해 생각해보자.
    만약 f(t1) < f(t2)라면 t1은 PQ의 top이 영원히 될수 없다.
    그러므로 이러한 t1은 전부 배제되었다고 가정하면,

    1. PQ안 원소들의 x값들을 순서대로 x1<x2<x3..라 하면
    2. f(x1)≥f(x2)≥f(x3)≥...을 만족한다.

    또한 위의 조건을 만족하도록 PQ를 관리하여야 한다.
    이러한 구조는 선형 deque로도 관리할수있으며, 매 원소는 최대 한 번 삽입과 삭제가 발생하게 되므로 이때의 시간 복잡도는 amortized O(NV)이다.

    현재 "f(x) = D[N-1,x]-x/v_{i}*c_{i} 라고 하자." 부분까지 코드로
    옮겨 보았습니다.

    int D[101][10001], N, i;
int v[101], c[101], k[101];
priority_queue<int> PQ;
inline int f(int x) {
    return D[N - 1][x] - x / v[i] * c[i];
}

inline int pack(int _N, int _V) {
    int x;
    for (i = 0; i < _N; i++)
        D[i][0] = 0;
    for (i = 0; i < _V; i++)
        D[0][i] = 0;

    for (i = 1, N = 1; i <= _N; N++, i++) {
        for (int V = 1; V <= _V; V++) {
            //1. f(V)값을 PQ에 넣는다.???
            //PQ.push(f(V));

            //D[N,V] = max{ D[N-1,x] - x/vi*ci } + V/vi*ci 부분
            for (int ki = 0; ki <= k[i] && v[i] * ki <= V; ki++) {
                x = V - v[i] * ki;
                D[N][V] = max(D[N][V], f(x));
            }
            D[N][V] += V / v[i] * c[i];

            //2. PQ의 top인 x값이 V와 vi*ki를 넘게 차이나면 top을 제거한다
            //while(PQ.top().x???? >=V와 vi*ki ??)
            //  PQ.pop();

            //3. PQ의 top인 f(x)값에 대해 D[N,V]=f(x)+V/vi*ci이다
            //f(x)값은 언제 큐에 들어간건지??
            //D[N][V] = PQ.top() + V / v[i] * c[i];
        }
    }
    return D[_N][_V];
}

    그 다음 설명부터 1,2,3 스텝을 코드로 옮기려고 하는데
    설명이 이해가 잘 안되서요. 1번 스텝에서 f(V)값을 PQ에 넣었는데
    2번 스텝에서 PQ.top()의 값이 x라는 부분이 잘 이해가 가지 않구요
    f(x)값은 언제 PQ에 넣어서 top에 있는지 잘 모르겠구요
    어디서 어떤 값들을 PQ에 push를 하는지 top을 제거를..
    설명이 잘 이해가 안가서 질문도 뭐라 해야할지 모르겠네요 ㅠ
    도와주세요ㅠ
    그리고 x \equiv V \bmod v_{i} 이 부분은 무슨 뜻인가요?


    9년 전
6개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    음 설명이 좀 불친절하게 적힌거같네요 죄송합니다;;
    1. PQ에는 f(x)와 x값을 구조체나 혹은 pair의 형태로 집어넣는다는 이야기입니다. 다만 PQ를 정렬할 때의 key값은 f(x)라고 생각하시면 됩니다. (x는 그 f(x)값이 너무 멀리 떨어진 위치의 값인지 아닌지 검사해주는 보조 정보라고 생각하시면 되어요)
    2. 만약 v_i = 3이고 V가 10이라면 x는 1 4 7 10... 이 될수있다는 이야기입니다


    9년 전 link
  • Elevista
    Elevista 

    priority_queue<Pair> PQ;
for (i = 1, N = 1; i <= _N; N++, i++) {
    for (int V = 1; V <= _V; V++) {
        //1. f(V)값을 PQ에 넣는다.
        PQ.push(Pair(f(V), V));

        //2. PQ의 top인 x값이 V와 vi*ki를 넘게 차이나면 top을 제거한다
        while (PQ.top().second > V && PQ.top().second > v[i] * k[i])
            PQ.pop();

        //3. PQ의 top인 f(x)값에 대해 D[N,V]=f(x)+V/vi*ci이다.
        D[N][V] = PQ.top().first + V / v[i] * c[i];
    }
}

    아니에요 제 머리가 빠가인걸요 ㅠ
    말씀듣고 소스코드 고쳐 보았는데요.
    205가 210으로, 37이 44로 오답이 나오네요..
    어디가 문제인 걸까요?
    2번 스텝이 틀렸나요? 아니면 1번 스텝이 틀렸는지.. 아니면 3번?..
    막막합니다 좌절중 ㅠ


    9년 전 link
  • Elevista
    Elevista

    \max\{ D[N-1, x]-x/v_{i}*c_{i} \} 연산을 어떻게 해야 lgV에 할 수 있는지 모르겠습니다..sigh


    9년 전 link
  • Kureyo
    Kureyo

    V와 v_i * k_i를 넘게 차이난다는 말은
    V - PQ.top().second > v[i]*k[i]를 말하는 것이었습니다(...)
    그리고 V는 0~v[i]-1 값에서부터 v[i]간격으로 뛰는 루프를 돌아야할것같습니다


    9년 전 link
  • Kureyo
    Kureyo

    예를 들면

    for (b=0;b<v[i];b++)
    {
    여기서 PQ clear
    for (V=b;V<_V;V+=v[i])
    {
    루프
    }
    }

    이런식으로 작성하여야할듯합니다


    9년 전 link
  • Elevista
    Elevista 

    for (i = 1, N = 1; i <= _N; N++, i++) {
    for (int b = 0; b < v[i]; b++) {
        priority_queue<Pair> PQ;
        for (int V = b; V <= _V; V += v[i]) {
            //1. f(V)값을 PQ에 넣는다.
            PQ.push(Pair(f(V), V));

            //2. PQ의 top인 x값이 V와 vi*ki를 넘게 차이나면 top을 제거한다
            while (V - PQ.top().second > v[i] * k[i])
                PQ.pop();

            //3. PQ의 top인 f(x)값에 대해 D[N,V]=f(x)+V/vi*ci이다.
            D[N][V] = PQ.top().first + V / v[i] * c[i];
        }
    }
}

    감사합니다 ㅠ 일단 정답은 뜨네요.
    이제 어떻게 돌아가는건지 열심히 봐야겠습니다.. 감사합니다 ㅠ


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.