이 글에서 다룰 문제는 아래와 같다.
1. \(N\)개의 물건의 가치 \(v_1, v_2, ..., v_n\)이 주어진다. \(W=\sum_{i=1}^N v_i\)로 정의한다.
2. 각 물건을 선택한 여부를 \(x_1, x_2, ..., x_n\)으로 정의한다.
3. \(\sum_{i=1}^N {v_ix_i} \sim O(N)\)을 만족한다.
4. \((\sum_{i=1}^N {v_ix_i})(W - \sum_{i=1}^N {v_ix_i})\)를 최대화 해야 된다.
문제를 다시 말하자면 각 물건을 두 그룹으로 나누고, 두 그룹의 속한 물건의 합의 곱을 최대화하는 문제이다.
이 문제의 naive한 풀이는 배낭 문제처럼 \(O(NW)\)에 해결할 수 있다. 한 그룹의 합이 \(X\)가 될 수 있는 여부를 알고 있다면 \(X(W-X)\)는 답의 후보가 된다.
여러가지 접근법을 살펴보면서 이 문제를 \(O(\frac{W\sqrt{N}}{32})\)에 해결해보자.
Bitset을 활용하여 \(O(\frac{NW}{32})\)에 해결하기
naive한 풀이에서 사용되는 \(dp_i\)의 정의는 "한 그룹의 합이 \(i\)가 될 수 있는 여부"로 정의된다. 아래의 방법으로 dp 테이블을 채울 수 있다.
1
2
3
4
|
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = w; j >= v[i]; j--)
dp[j] |= dp[j - v[i]];
|
cs |
\(dp\) 테이블을 비트의 관점으로 생각 해보자. 만약 \(v = {1, 3, 4}\)로 정의하고 문제를 해결한다면 \(dp\) 테이블의 형태는 아래와 같이 이루어진다. 우측부터 한 그룹의 합 \(0\)이 가능한 여부를 나타낸다.
\(v=0, 000000001\)
\(v=1, 000000011\)
\(v=3, 000011011\)
\(v=4, 110111011\)
현재 비트에서 수 \(v\)를 넣게 된다면 현재 비트에서 \(v\)만큼 시프트한 것과 or한 형태로 전이된다. 즉 아래와 같이 전이된다.
\(dp_i |= (dp_{i-1} << v[i])\)
길이가 \(W\)인 bitset을 시프트하는 연산은 \(O(\frac{W}{32})\)에 이루어진다. 그러므로 이 문제를 \(O(\frac{NW}{32})\)에 해결할 수 있다.
1
2
3
4
|
bitset<W> dp;
dp.set(0);
for (int i = 0; i < n; i++)
dp |= (dp << v[i]);
|
cs |
Bounded Knapsack Problem (BKP) 해결하기
위키피디아에서 정의된 Bounded Knapsack Problem(BKP)의 정의는 아래와 같다.
1. \(N\)개의 물건의 가치 \(v_1, v_2, ..., v_n\)이 주어진다.
2. 각 물건은 최대 \(C\)번 중복해서 넣을 수 있다. 각 물건을 담은 횟수를 \(x_1, x_2, ..., x_n\)으로 정의한다.
3. \(\sum_{i=1}^N {v_ix_i} \le W\)을 만족하면서 \(\sum_{i=1}^N {v_ix_i}\)을 최대화 해야 된다.
(유사한 문제로는 BOJ 12920 평범한 배낭 2 문제가 있다.)
naive한 접근은 \(CN\)개의 물건으로 나누어 배낭 문제를 해결하면 \(O(CNW)\)에 해결할 수 있다. 만들 수 있는 가치 중 \(w \le W\)의 최댓값을 찾으면 해결할 수 있다.
각 물건을 한개씩 나누는 것보다 \(2^K\) 꼴로 나누게 된다면 모든 경우를 고려할 수 있고, 최대 \(O(logC)\)개의 물건이 생기게 된다. 그러므로 \(O(NWlogC)\)에 해결할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
vector<int> nv;
for (int i = 0; i < n; i++) {
int nc = c;
for (int j = 0; (1 << j) <= nc; j++) {
nv.push_back((1<<j)*v[i]);
nc -= (1 << j);
}
nv.push_back(nc*v[i]);
}
dp[0] = 1;
for (int i = 0; i < nv.size(); i++)
for (int j = w; j >= nv[i]; j--)
dp[j] |= dp[j - nv[i]];
|
cs |
본 문제 해결하기
본 문제를 해결하는 방법은 위의 두가지 접근 방법을 모두 적용하면 해결할 수 있다.
문제에서 주어진 수들을 {숫자, 숫자가 나타난 횟수}로 정리하여 Bounded Knapsack Problem을 bitset을 적용하여 풀면 \(O(\frac{W\sqrt{N}}{32})\)에 해결할 수 있다. 아래는 전체 구현 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
using namespace std;
const int W = 100001;
typedef pair<int, int> pi;
#define num first
#define cnt second
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n; cin >> n;
vector<int> num(n);
int sum = 0;
for (int& p : num) cin >> p, sum += p;
sort(num.begin(), num.end());
vector<pi> arr;
for (int i = 0; i < n;) {
pi ret = pi(num[i], 0);
int j = i;
while (j < n && num[i] == num[j])
ret.cnt++, j++;
arr.push_back(ret);
i = j;
}
bitset<W> dp;
dp.set(0);
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; (1 << j) <= arr[i].cnt; j++) {
dp |= (dp << (arr[i].num*(1 << j)));
arr[i].cnt -= (1 << j);
}
dp |= (dp << (arr[i].num*arr[i].cnt));
}
long long ans = 0;
for (int i = 0; i <= sum; i++)
if (dp[i]) ans = max(ans, 1LL * i * (sum - i));
cout << ans;
return 0;
}
|
cs |
각 단계마다 \(O(log{C_i})\)번 수행 된다. 하지만 본 문제의 3번 조건 때문에 \(\sum_{i=1}^N {log{C_i}} = O(\sqrt{N})\)이 보장된다. 그러므로 \(O(\frac{W\sqrt{N}}{32})\)에 해결할 수 있다.
자세한 증명은 이 링크에서 확인할 수 있다.
연습 문제
센트로이드인 정점에서 해결해야 되는 문제는 이 글에서 나온 문제와 동일하다.