解法
分散 \(V\) の最小化． \(V = \frac{\sum_{i \in D} (x_{i} - \overline{x})^{2} }{D}\) を最小化する．\(\overline{x}\) は，振り分け方と無関係な定数． よって， \(\,(x_{i}-\overline{x})^{2}\,\)の最小化をすれば十分．
\(D,N\)が小さいので全探索したい．
\(dp[i][s] := \) \([0,i)\)まで袋につめた, まだ残っている商品の集合が \(s \in 2^{N}\) のときの \(V\)の min
とする． 遷移が重要で，\(t \subset s\) に対して， \(min(dp[i+1][s^t], dp[i][s] + a[s])\) と遷移する． ただし，\(a[s] := \sum_{i \in s} (x_{i} - \overline{x} )^{2} を前計算しておく．
計算量は， 前計算 \(O(N 2^{N})\), 後計算 \(O(D3^{N})\).
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,d;
cin >> n >> d;
vll a(n); rep(i,n) { cin >> a[i]; }
double ave = 0;
rep(i,n) ave += a[i];
ave /= (double)d;
rep(s,1LL<<n){
rep(i,n) if(s>>i&1){
sum2[s] += a[i];
}
sum2[s] = square(sum2[s]-ave);
}
dp[(1LL<<n)-1] = 0;
rep(i,d){
swap(dp, old);
drep(s,1LL<<n){
for(ll t = s; t >= 0; t--){
t = t & s;
chmin(dp[s^t], old[s] + sum2[t]);
}
}
}
printf("%.10lf", dp[0]/(double)(d));
return 0;
}
