幸运背包 题解

解题思路

1. 方差公式化简

方差定义为：

V = (1/D) * Σ(x_i - x̄)²

展开得：

V = (1/D) * Σx_i² - x̄²

因为所有物品总重量 S = ΣW_i 固定，所以平均值 x̄ = S/D 是常数。最小化方差等价于最小化 Σx_i²（各福袋重量平方和）。

2. 状压 DP

数据范围 N ≤ 15，用二进制状态压缩。

状态定义：

• dp[mask][k]：将 mask 集合中的物品分成 k 个福袋时，各福袋重量平方和的最小值。

预处理：

• sum[mask]：子集 mask 中所有物品的总重量。

转移方程：

dp[mask][k] = min(dp[mask ^ sub][k-1] + sum[sub]²)，其中 sub 是 mask 的非空子集。

枚举最后一个福袋 sub，剩下的物品分成 k-1 组。

边界条件：

• dp[0][k] = 0（空集合分成 k 组，平方和为 0）

最终答案：

ans = dp[full][D] / D - (S/D)²

3. 复杂度

枚举子集的子集总复杂度 O(3^N)，对于 N=15，3^15 ≈ 1400 万，2 秒内可跑完。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,d;
    cin>>n>>d;
    vector<ll>w(n);
    ll s=0;
    for(int i=0;i<n;i++){
        cin>>w[i];
        s+=w[i];
    }
    int full=(1<<n)-1;
    vector<ll>sum(1<<n,0);
    for(int m=1;m<(1<<n);m++){
        int low=m&(-m);
        int i=__builtin_ctz(low);
        sum[m]=sum[m^low]+w[i];
    }
    const ll INF=1e18;
    vector<vector<ll>>dp(1<<n,vector<ll>(d+1,INF));
    for(int k=0;k<=d;k++)dp[0][k]=0;
    for(int m=1;m<=full;m++){
        for(int k=1;k<=d;k++){
            for(int t=m;t;t=(t-1)&m){
                if(dp[m^t][k-1]!=INF){
                    dp[m][k]=min(dp[m][k],dp[m^t][k-1]+sum[t]*sum[t]);
                }
            }
        }
    }
    ll ms=dp[full][d];
    lll num=(lll)ms*d-(lll)s*s;
    lll den=(lll)d*d;
    double ans=(double)num/(double)den;
    if(ans<0)ans=0;
    printf("%.15f\n",ans);
    return 0;
}