[[problem: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개의 t_{1} < t_{2}에 대해 생각해보자.
만약 f(t_{1}) < f(t_{2})라면 t_{1}은 PQ의 top이 영원히 될수 없다.
그러므로 이러한 t_{1}은 전부 배제되었다고 가정하면,
1. PQ안 원소들의 x값들을 순서대로 x_{1}<x_{2}<x_{3}..라 하면
1. f(x_{1})≥f(x_{2})≥f(x_{3})≥...을 만족한다.

또한 위의 조건을 만족하도록 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}$ 이 부분은 무슨 뜻인가요?