只要枚举左右两个子天平砝码的集合，我们就能算出左右两个悬挂点到根悬挂点的距离。
但是题中要求找尽量宽的天平但是不能超过房间的宽度，想不到要怎样记录结果。
参考别人代码，用了一个结构体的vector，保存每个集合合法方案的左右两端最长的距离。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <map> 6 #include <cmath> 7 #define MP make_pair 8 #define Ft first 9 #define Sd second 10 using namespace std; 11 12 typedef pair<double, double> PDD; 13 14 const int maxn = 10; 15 const int maxs = 1000; 16 17 vector<PDD> tree[maxs]; 18 19 int n; 20 double r; 21 double a[maxn], w[maxs]; 22 bool vis[maxs]; 23 24 int bitcount(int x) 25 { 26 int ans = 0; 27 while(x) { ans += (x & 1); x >>= 1; } 28 return ans; 29 } 30 31 void dfs(int S) 32 { 33 if(vis[S]) return ; 34 vis[S] = true; 35 if(bitcount(S) == 1) { tree[S].push_back(MP(0, 0)); return ; } 36 37 PDD t = MP(0, 0); 38 for(int s1 = (S-1)&S; s1; s1 = (s1-1)&S) 39 { 40 int s2 = S ^ s1; 41 dfs(s1); dfs(s2); 42 double x1 = w[s2] / w[S], x2 = w[s1] / w[S]; 43 for(int i = 0; i < tree[s1].size(); i++) 44 for(int j = 0; j < tree[s2].size(); j++) 45 { 46 t.Ft = max(x1 + tree[s1][i].Ft, tree[s2][j].Ft - x2); 47 t.Sd = max(x2 + tree[s2][j].Sd, tree[s1][i].Sd - x1); 48 if(t.Ft + t.Sd < r) tree[S].push_back(t); 49 } 50 } 51 } 52 53 int main() 54 { 55 int T; scanf("%d", &T); 56 while(T--) 57 { 58 scanf("%lf%d", &r, &n); 59 for(int i = 0; i < n; i++) scanf("%lf", a + i); 60 int all = (1 << n) - 1; 61 62 for(int i = 0; i <= all; i++) 63 { 64 w[i] = 0; 65 tree[i].clear(); 66 for(int j = 0; j < n; j++) if(i & (1 << j)) 67 w[i] += a[j]; 68 } 69 70 memset(vis, false, sizeof(vis)); 71 dfs(all); 72 double ans = -1; 73 for(int i = 0; i < tree[all].size(); i++) ans = max(ans, tree[all][i].Ft + tree[all][i].Sd); 74 if(ans < 0) puts("-1"); 75 else printf("%.9f ", ans); 76 } 77 78 return 0; 79 }