题意：给出房间的宽度r和s个挂钩的重量。设计一个尽量宽，但宽度不超过房间宽度的天平，挂着所有的挂钩。挂钩的宽度不计，且不相同的挂钩可以互相重叠
思路：每次将当前集合分成两个不相交的子集合，每次都构造出子集的最大的天平，最后从子集中选出最大的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 65;
double r,w[10],value[MAXN],ans;
struct node{
double l1,l2;
}nw;
vector<node> adj[MAXN];
int vis[MAXN],num[MAXN],n;
void dfs(int state){
double l1,l2;
bool flag = false;
if (vis[state])
return;
vis[state] = true;
for (int i = (state&(state-1)); i > 0; i = ((i-1)&state)){
int j = state ^ i;
dfs(i);
dfs(j);
for (int s = 0; s < num[i]; s++)
for (int p = 0; p < num[j]; p++){
l1 = value[j] / (value[i]+value[j]);
l2 = value[i] / (value[i]+value[j]);
nw.l1 = max(adj[i][s].l1+l1,adj[j][p].l1-l2);
nw.l2 = max(adj[i][s].l2-l1,adj[j][p].l2+l2);
if (nw.l1 + nw.l2 <= r){
adj[state].push_back(nw);
num[state]++;
}
}
flag = true;
}
if (!flag){
nw.l1 = nw.l2 = 0;
adj[state].push_back(nw);
num[state]++;
}
}
int main(){
int t;
scanf("%d",&t);
while (t--){
scanf("%lf%d",&r,&n);
for (int i = 0; i < n; i++)
scanf("%lf",&w[i]);
for (int i = 0; i < (1<<n); i++){
adj[i].clear();
value[i] = 0;
for (int j = 0; j < n; j++)
if (i & (1<<j))
value[i] += w[j];
}
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
dfs((1<<n)-1);
ans = -1;
for (int i = 0; i < num[(1<<n)-1]; i++){
if (adj[(1<<n)-1][i].l1 + adj[(1<<n)-1][i].l2 > ans)
ans = adj[(1<<n)-1][i].l1 + adj[(1<<n)-1][i].l2;
}
printf("%.20f\n",ans);
}
return 0;
}