[ABC332E] Lucky bag 题解
__ryp__
·
·
题解
谨此纪念我的第一道蓝题题解（虽然是看了其他题解后写的）
题意
给定一个序列 W_0 \cdots W_{n - 1}，以及一个整数 D，要求把 W 的所有元素分配到 D 个盒子中，求分配的方差和最小值。
分析
很明显是动态规划题。我们可以设 f(i,j)，表示将状态 j 所表示的元素分配到 i 个盒子中的最小方差（\sum_k^i (x_k-\bar x)^2）。
分析边界：
$$f(i, j)=\sum\limits_k^0 (x_k-\bar x)^2=(x_k-\bar x)^2 \quad i = 0$$
对于一般情况，要将 $j$ 所表示的元素放进 $i$ 个盒子中，我们要考虑 $j$ 的每个子状态 $k$：找将 $s$ 与 $k$ 差的元素放进 $i - 1$ 个盒子中所得到的最小方差和再加上 $k$ 状态的方差，以上的最小值，也就是
$$f(i, j) = \min\limits_{k\in j}{f(i-1,j\oplus k)+(x_k-\bar x)^2}$$
因此
$$f(i,j) = \begin{cases}
(x_j - \bar x)^2 & i = 0 \\
\min\limits_{k\in j} f(i-1,j\oplus k)+(x_k - \bar x)^2 & \text{otherwise}
\end{cases}$$
## 证明
证明是彻底理解转移方程原理的很好方式。
首先易证本问题有最优子结构：
### 最优子结构证明
问题就是求 $\frac{1}{D}\min\sum\limits_{i=0}^D(x_i-\bar x)^2$。设 $T$ 是问题的最优解，要证 $\sum\limits_{i=1}^D(T_i-\bar x)^2$ 也最小。
反证。设 $U_1,\cdots,U_{D-1}$ 是一个更优的方案，即
$$
\sum\limits_{i=1}^D(T_i-\bar x)^2 > \sum\limits_{i=1}^D(U_i -\bar x)^2
$$
那么可以有
$$
T' = \frac{1}{D}((T_1-\bar x)^2+\sum\limits_{i=1}^D(U_i-\bar x)^2)
$$
则必有 $T' < T$，与 $T$ 是本问题的最优解冲突。故不存在比 $T_1, \cdots T_{D-1}$ 更优的方案 $U$，得证。
------------
以上是证明最优子结构的常用方法，即《算法导论》中所讲的 copy-paste 法。
## 代码
代码预计算出了 $\bar x$ 与 每一种状态 $k$ 对应的 $x_k$，然后就是状压 DP。
```c++
#include <iostream>
using namespace std;
#define rep(v, s, e) for (auto v = (s); v < (e); v++)
#define square(x) ((x) * (x))
const int N = 15, M = 1 << 15;
long long *w;
long long s[M];
double f[N][M];
long long
read (void)
{
long long res = 0;
char c;
while (!isdigit (c = getchar ()));
do res = res * 10 + c - '0'; while (isdigit (c = getchar ()));
return res;
}
int
main (void)
{
int n, d; n = read (); d = read ();
double xbar = 0;
w = new long long [n];
rep (i, 0, n) xbar += w[i] = read ();
xbar /= d;
rep (i, 0, 1 << n) rep (j, 0, n + 1)
s[i] += w[j] * !!(i & (1 << j));
rep (i, 0, 1 << n) f[0][i] = square (s[i] - xbar);
rep (i, 1, d) rep (j, 0, 1 << n)
{
f[i][j] = f[i - 1][j] + square (xbar);
for (int k = j; k; k = (k - 1) & j)
f[i][j] = min (f[i][j], f[i - 1][j ^ k] + square (s[k] - xbar));
}
printf ("%.10lf\n", f[d - 1][(1 << n) - 1] / d);
return 0;
}
```
## 补充最优解
以上代码 [不是最优解 （235ms）](https://www.luogu.com.cn/record/139605822)。
最优解使用的是另一种动态规划的实现方法，即自上到下的动态规划。在某些情况下这可以省去很多的计算。采用这种方法可以得到 13ms 的[最优解](https://www.luogu.com.cn/record/139174465)。
------------
upd. 2023/12/15 增加最优解
------------
证明有错误或叙述不当的请指出。感谢。