各福袋に入ったグッズの重さの合計の平均値 \(\bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D)=\frac{1}{D}(W_1+W_2+\cdots+W_N)\) はグッズの分け方によらないことに注意してください。
また、以下では \(i\) 個目のグッズを単にグッズ \(i\) と表記します。

この問題を動的計画法によって解くことを考えます。
\(\{1,2,\ldots,N\}\) の部分集合 \(S\) および \(1\leq k \leq D\)をみたす整数 \(i\) について、\(dp[S][k]\) を、 \(g\in S\) であるようなグッズ \(g\) からなるグッズの集合を \(k\) 個の福袋に分けるような方法のうち、それぞれの福袋に入ったグッズの重さの合計を \(y_1,y_2,\ldots,y_k\) としたときの \(\displaystyle\sum_{i=1}^k (y_i-\bar{x})^2\) の値 の取りうる最小値として定義します。 ここで、\(\bar{x}\) は上で述べた入力から直ちに一意に定まる値のことであり、\(S\) や \(k\) に依存する値ではないことに注意してください。 最終的な答えは、\(dp[\{1,2,\ldots,N\}][D]\) を \(D\) で割った値として求めることができます。

まず、\(dp[S][1]\) の値については、福袋が \(1\) つの場合は集合に属する全てのグッズをその福袋に入れるしかないため、求める値は \(\left(\left(\displaystyle\sum_{g\in S}W_g\right)-\bar{x}\right)^2\) と なります。
次に、\(2\leq k\leq D\) として、任意の集合 \(S'\subset \{1,2,\ldots,N\}\) および正整数 \(k'\leq k-1\) について \(dp[S'][k’]\) が求まっているとして、\(dp[S][k]\) の値を求める方法について考えます。 このとき、求める値が最小となるような \(k\) 個の福袋への分け方のうち適当に一つの福袋を選んで分けて考えることで、これは、

\[ dp[S][k]=\min_{T\subseteq S} (dp[(S-T)][k-1]+dp[T][1]) \]

として求まることが分かります。ただし、ここで、\((S-T)\) は差集合 \((S-T)=(S\backslash T)=\{x|x\in S \land x\notin T\}\) を表します。 これを\(k=2,3,\ldots,D\) の順で繰り返すことにより、最終的な答えを得ることができます。

次に計算量について、\(dp[S][1]\) の値は各 \(S\) に対して \(O(N)\) で求められる事から \(O(N2^N)\) の計算量で求められるため問題ありません。

集合 \(S\) のサイズを \(\lvert S\rvert\) で表すとすると、 \(T\subseteq S\) をみたす \(T\) の候補は \(2^{\lvert S\rvert}\) 個考えられます。よって、特定の \(S\) および \(2\leq k\leq D\) に対してすでに求まっている\(dp[S'][k’]\) \((S'\subset \{1,2,\ldots,N\}, k'\leq k-1)\) から \(dp[S][k]\) の値を求めるためには \(k\) によらず \(2^{|S|}\) 回の計算を行う必要があります。 \( \{1,2,\ldots,N\}\) の部分集合のうちサイズが \(s\) であるものは \({}_NC_s\) 個ある事から、\(k\) の取り得る範囲にも注意して、全体での計算回数は

\[ \left(\displaystyle\sum_{s=0}^N {}_NC_s\times 2^s \right)\times (D-1) =(2+1)^N\times(D-1)< 3^N\times D \]

となり、\(D\leq N\leq 15\) で\(3^N\times D\leq 2.2\times 10^8\) であることから、操作も単純な加算および比較のみであることとあわせて十分間に合います。
よってこの問題を解くことができました。

以下は実装時の注意事項です。

• 集合を直接添字として持つと基本的に実行速度は遅くなるため、それぞれの要素が含まれるかどうかを表すビット列で管理すると良いでしょう。
• 上記のようなビット列で集合を管理する時、ビット列 \(x\) に対応する集合の部分集合(に対応するビット列)の列挙は \(y=x\) から始めて \(y\) を \( (y-1)\& x\) に変更する操作を \(y=0\) になるまで繰り返すことでできます。 （途中で登場した \(y\) が \(x\) に対応する集合の部分集合に対応するビット列を過不足なく列挙しています。）ここで、\(\&\) は論理積を表しています。 証明はここでは省略します。
• 出力の桁数に注意してください。例えば \(6\) 桁以下しか出力していない場合、誤差によってWAとなる可能性があります。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n,d,x;
	long double w[15];
	long double ave=0;
	long double dp[(1<<15)][16];
	long double y;

	cin>>n>>d;
	for(int i=0;i<n;i++)cin>>w[i],ave+=w[i];
	ave/=((long double)d);
	for(int i=0;i<(1<<n);i++){
		y=0;
		for(int j=0;j<n;j++){
			if(i&(1<<j))y+=w[j];
		}
		dp[i][1]=pow(y-ave,2);
		for(int j=2;j<=d;j++){
			dp[i][j]=dp[i][j-1]+dp[0][1];
			x=i;
			while(x>0){
				dp[i][j]=min(dp[i][j],dp[i-x][j-1]+dp[x][1]);
				x=(x-1)&i;
			}
		}
	}
	cout<< setprecision(10) <<(dp[(1<<n)-1][d]/((long double)d))<<endl;
	return 0;
}