[19696] Knapsack

난이도: Platinum IV

 

태그

• Dynamic Programming → Knapsack (냅색 문제)
• Mathematics (수학)
• Greedy (그리디)
• Harmonic Sequence

 

풀이

1. 한 종류의 물건이 여러 개 있는 냅색은 어떻게 풀까?

가치가 \( v \)이고 무게가 \( w \)인 물건이 \( k \)개가 있다면,

그냥 \( (v, w) \)를 \( k \)개 만들어두면 됩니다.

 

하지만 이렇게 하면 물건의 개수가 \( NK \)개가 되니까, 너무 많아집니다.

 

2. (from [1]) 물건의 개수를 줄일 수 없을까?

1개씩 놓는 건 아무래도 공간 낭비인 것 같습니다.

대신에, 2의 제곱수를 사용해서 더 편하게 표현해봅시다.

이게 무슨 소리냐고요?

 

어떤 물건이 \( 15 \)개 있었다고 해봅시다.

그럼, 저희는 그 물건을 \( 0 \)개부터 \( 15 \)개까지 구매할 수 있습니다.

그런데 이를 위해 \( 1 \)개짜리 물건을 \( 15 \)개 만드는 대신

\( 1 \)개짜리 묶음 하나, \( 2 \)개짜리 묶음 하나, \( 4 \)개짜리 묶음 하나, \( 8 \)개짜리 묶음 하나 를 만들면?

이 4개의 묶음만으로도 \( 0 \)개부터 \( 15 \)개까지의 구매 방식을 만들어낼 수 있습니다.

(2진수를 생각해보세요.)

 

하지만 이 접근을 바로 사용하기 전에, 주의해야 할 게 있습니다.

만약 물건이 \( 49 = 32 + 16 + 1 \)개 있다면, \( 32, 16, 1 \)에 해당하는 것만 만들면 될까요?

물론 아니오입니다. 저대로라면 \( 2 \)개나 \( 18 \)개 등등을 표현할 수 없으니까요.

 

하지만 그렇다고 \( 1, 2, 4, 8, 16, 32 \)를 다 만들어둔다면, \( 50 \)개나 \( 63 \)개 등등이 가능해져버리게 됩니다.

그럼 어떻게 해야 할까요?

 

해답은, \( 1, 2, \ldots \)로 올라가다가 합을 넘어버리는 시점이 되면

그냥 다시 \( 1 \)부터 올라가기 시작하면 됩니다.

 

즉, \( 49 \)는 \( (1 + 2 + 4 + 8 + 16) + (1 + 2 + 4 + 8) + (1 + 2) \)로 표현되겠죠.

이렇게 하면, \( 0 \)부터 \( 49 \)까지의 모든 수를 표현함 (각각 0 ~ 31, 0 ~ 15, 0 ~ 3을 표현할 수 있으니)과 동시에

\( 50 \) 이상의 수는 표현할 수 없게 됩니다. (최대가 \( 49 \)니까요.)

 

이렇게 하면 \( k \)개의 물건을 \( O(\log^2 k) \)개의 물건만 사용해서 표현할 수 있습니다.

 

Intermission 1. 물건 개수를 잘 처리한 거 같으니, 이제 냅색을 돌려도 되나?

냅색의 시간복잡도는 O((최대 무게) × (물건의 개수)) 입니다.

지금까지 구한 걸 기준으로 보면, \( O(S \times N \log^2 K) \)가 되겠죠.

 

아무래도 아직 냅색을 돌리기에는 시간이 너무 오래 걸릴 것 같습니다.

 

3. 잠깐 생각해보자: 모든 물건의 무게가 동일할 때의 냅색

모든 물건의 무게가 \( w \)로 동일한 냅색을 돌려봅시다.

그럼, 최대 허용 무게가 \( S \)일 때 총 \( \left\lfloor \frac{S}{w} \right\rfloor \)개의 물건을 넣을 수 있게 됩니다.

또한, 사실상 무게를 신경쓰지 않아도 되니, 가치가 높은 물건부터 그리디하게 사용하면 되겠죠.

 

4. [3]의 접근을 사용해서, 물건의 개수를 더 줄여보자.

무게가 \( w \)인 물건들은, 최대 \( \left\lfloor \frac{S}{w} \right\rfloor \)개만 사용할 수 있습니다.

그리고, 이 물건들 중에서는 가장 가치가 높은 \( \left\lfloor \frac{S}{w} \right\rfloor \)개의 물건을 들고 와야겠죠.

 

그러니, 물건들을 일단 만든 뒤, 각각의 무게 \( w \)에 대해 가치가 가장 높은 \( \left\lfloor \frac{S}{w} \right\rfloor \)개를 제외하고는 그냥 버립시다.

 

이렇게 하면, 무게 \( w \)의 물건은 최대 \( \left\lfloor \frac{S}{w} \right\rfloor \)개만 남게 되므로, 최종적으로 남게 되는 물건의 수는 \( \sum\limits_{w=1}^{S} \left\lfloor \frac{S}{w} \right\rfloor \)개, 즉 \( O(S \log S) \)개가 남게 됩니다.

 

코드

남은 건 (최대 무게) × (물건 개수)의 시간, 즉 \( O(S^2 \log S) \)의 시간으로 냅색을 돌리는 일이죠.

priority_stack<ll> pq[2020];
 
ll dp[2020];
 
void Main(){
    int n, m; cin >> m >> n;
    for (int i = 1; i <= n; i++){
        ll v, w, c; cin >> v >> w >> c;
        ll num = 1; while (c){
            if (num > c){ num = 1; } c -= num;
            ll ww = w*num; if (ww > m){ break; }
            ll vv = v*num;
            pq[ww].push(vv); if (pq[ww].size() > m/ww){ pq[ww].pop(); }
            num *= 2;
        }
    }
    for (int w = 1; w <= m; w++){
        while (!pq[w].empty()){
            ll v = pq[w].top(); pq[w].pop();
            for (int i = m; i >= w; i--){ dp[i] = max(dp[i], dp[i-w]+v); }
        }
    }
    cout << *max_element(dp, dp+m+1);
}