#include <iostream> #include <cstring> #include <vector> using namespace std; const int MAX = 6; struct Tree{ double L, R; //树的左边和右边的长度 Tree():L(0), R(0){} }; double width, w[MAX], sum[1<<MAX]; int vis[1<<MAX]; vector<Tree> tree[1<<MAX]; //枚举出来的结点可以组合成多个树 void dfs(int subset); //枚举二叉树 int main(){ freopen("input.txt", "r", stdin); int T; cin >> T; while(T--){ int s; scanf("%lf%d", &width, &s); for(int i=0; i<s; i++){ scanf("%lf", &w[i]); } //初始化 memset(sum, 0, sizeof(sum)); for(int i=1; i<(1<<s); i++){ tree[i].clear(); //清空树 int k = 1; for(int j=0; j<s; j++){ //算出当前集合所有结点的重量和 if(k & i){ sum[i] += w[j]; } k = (k << 1); } } //进行枚举 int root = (1<<s) - 1; memset(vis, 0, sizeof(vis)); dfs(root); //得到最大的答案 double ans = -1; for(int i=0; i<tree[root].size(); i++){ ans = max(tree[root][i].L + tree[root][i].R, ans); } printf("%.10lf\n", ans); } } void dfs(int subset){ if(vis[subset]) return; vis[subset] = 1; bool hasChild = false; for(int left = ((subset-1) & subset); left > 0; left = ((left-1) & subset)){ //枚举集合 hasChild = true; int right = subset ^ left; //left 的补集 double l = sum[right] / sum[subset]; //左臂长度 double r = sum[left] / sum[subset]; //右臂长度 dfs(left); dfs(right); //把左右树的子树也枚举出来 for(int i=0; i<tree[left].size(); i++){ //将枚举出的左右子树组合起来 for(int j=0; j<tree[right].size(); j++){ Tree t; t.L = max(tree[left][i].L + l, tree[right][j].L - r); t.R = max(tree[right][j].R + r, tree[left][i].R - l); if(t.L + t.R < width){ //如果满足条件,枚举结果加一 tree[subset].push_back(t); } } } } if(!hasChild){ //叶子结点的左右臂为零 tree[subset].push_back(Tree()); } }