【题解】P3878 [TJOI2010]分金币

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

给定\(n\)个数，第\(i\)个数为\(v_i\)。

现在要把它分成数目之差不超过1的两部分，问这样的两部分数字和之差最小是多少？

\(n \le 30\)

分析

由于\(n\)较小，想到暴力枚举答案。

转移： \[ f(i,j,k) \rightarrow \begin{cases} f(i,j+a_i,k+1)\\ f(i+1,j,k) \end{cases} \]

继续优化，由于题目要求的是平分，所以可以先分成两组，然后每次选两个数交换，直到答案最优为止。具体怎样交换呢？点开题目标签，发现可以使用模拟退火。

模拟退火可以在一种范围内求多峰函数的最值。温度越高，解的变化量越大；反之则逐渐变小，且解逐渐集中在最优解附近，最后达到设定最低温，大部分情况，当前取得的解就是最优解。

在本题中，我们不断随机要交换的两数的位置，统计答案并记录最大值。如果新解比原来的最大值大，接受答案；否则以一定概率选择接受答案。

实现

统计答案的函数：

1
2
3
4
5
6
int anss() {
    ll sum1 = 0, sum2 = 0; //sum1为第一组的和，sum2为第二组的和
    for (int i = 1; i <= (n + 1) / 2; i++) sum1 += v[i];
    for (int i = (n + 1) / 2 + 1; i <= n; i++) sum2 += v[i];
    return abs(sum1 - sum2);
}

下面是模拟退火的部分：

首先需要定义初始温度\(s\)，结束温度\(f\)，每次温度的减少量参数\(chT\)。 不超时的情况下调高初始温度，调低最终温度，调大\(chT\)。

1
double s = 5000, f = 1e-10, chT = 0.91; //参考值

接下来需要实现按一定概率接受答案：

1
if((exp((ans - sum) / i)) < (double(rand()) / RAND_MAX)) swap(v[x], v[y]);

exp(x)函数可以返回\(e^x\)

The exp() function returns e (2.7182818) raised to the argth power. ——c++参考手册

exp()函数图像

当\(exp()\)在\(x<0\)时，\(y\)一定为\(0-1\)之间的小数且单调递增，而(double(rand()) / RAND_MAX))也是一个\(0-1\)之间的随机小数。这样，温度越小，接受当前解的几率就越低，答案就越趋近于最大值。

最后别忘记在main()里种随机数种子：srand((int)time(0));

附完整代码（\(2.5s\) \(648.00kb\)）

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>

using namespace std;
#define ll int
const ll N = 35, inf = 2147483647;
ll n, v[N], t, ans;

ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int anss() {
    ll sum1 = 0, sum2 = 0;
    for (int i = 1; i <= (n + 1) / 2; i++) sum1 += v[i];
    for (int i = (n + 1) / 2 + 1; i <= n; i++) sum2 += v[i];
    return abs(sum1 - sum2);
}

void sa() {
    double s = 5000, f = 1e-10, chT = 0.91;
    for (double i = s; i > f; i *= chT) {
        ll x = rand() % n + 1, y = rand() % n + 1;
        swap(v[x], v[y]);
        ll sum = anss();
        if (sum < ans) ans = sum;
        else {
            if ((exp((ans - sum) / i)) < (double(rand()) / RAND_MAX)) swap(v[x], v[y]);
        }
    }
}

int main() {
    srand((int) time(0));
    t = read();
    while (t--) {
        ans = inf;
        n = read();
        for (int i = 1; i <= n; i++) v[i] = read();
        for (int i = 1; i <= 1000; i++) sa();
        cout << ans << endl;
    }
    return 0;
}